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 thatwhp(with high probability) in G~ the first triangle appears before the graph is connected

2)

let be a constant.

prove thatwhpa random graph G(n,m) (random graph with n vertices and m edges), with 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 such that 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 thatwhpin 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)

- the biggest group of independent vertices of G

- the biggest klik G

next questions soon

10x