## random graphs questions

1)
let G~ be a random graph process
(random graph process -
taking all possible edges in G of n vertices,
giving them order by a member of S(n*(n-1)), and at each stage adding the next edge
)
prove that whp (with high probability) in G~ the first triangle appears before the graph is connected

2)
let $\displaystyle \epsilon>0$ be a constant.
prove that whp a random graph G(n,m) (random graph with n vertices and m edges), with $\displaystyle m=n*(1+\epsilon)$ is not planar
(planar - the graph can be drew on 2D without any edges crossing each other)

3)
let H be a graph with a cycle.
prove that there exist a constant $\displaystyle a=a(H)>0$ such that $\displaystyle t(n,H) >= n ^ \((1+a)$ for all suficently large n.
where t(n,H) is the Turan number of H, which is the maximun number of edges in a H-free graph on n vertices

4)
prove that whp in G(n,0.5) (G(n,p) - a random graph with n vertices and a probability of p to generate each edge. the probability is independent)
$\displaystyle a(G),w(G) = (1+o(1))2 * ln(n)/ln(2)$

$\displaystyle a(G)$ - the biggest group of independent vertices of G
$\displaystyle w(G)$ - the biggest klik G

next questions soon

10x