A RANDOM GRAPH MODEL
A RANDOM GRAPH MODEL LEMMA:1.1 A random graph G_(n,p), given that its number of edges is m, is equally likely to be one of the (((n¦2))¦m) graph that have m edges. Proof: Let G_0 be any labelled graph with m edges. Then since {G_(n,p)= G_0 }⊆{|E_(n,p) |=m} We have P(G_(n,p)= G_0 |E_(n,p) |=m)= (P(G_(n,p)= G_0 |E_(n,p) |=m))/(P(|E_(n,p) |=m)) = P(G_(n,p)= G_0 )/((|E_(n,p) |=m) ) = (p^m (1-p)^((n¦2)-m ))/(〖(((n¦2))¦m) p〗^m (1-p)^((n¦2)-m ) ) = (((n¦2))¦m)^(-1). Thus G_(n,p) conditional on the event {G_(n,p) has m edges} is equal in distribution to G_(n,m), the graph chosen uniformly at random from all graphs with m edges. Obviously, the main difference between those two models of random graph is that in G_(n,m.)we choose its number of edges, while in the case of G_(n,p) the number of edges is the binomial random variable with the parameters and p. intuitively, for large n random graphs G_(n,m) and G_(n,p) should behave in similar fashion when the number of edges m in G_(n,m