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 \epsilon>0 be a constant.
prove that whp a random graph G(n,m) (random graph with n vertices and m edges), with 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 a=a(H)>0 such that 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)
a(G),w(G) = (1+o(1))2 * ln(n)/ln(2)

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

next questions soon

10x