Monday, October 20, 2008

Re: Doubt on random graphs

Sorry. The 1/2*N^2 is a mistake  That is the *total number* of edges in a complete graph. k is the average degree--i.e. the number of edges each vertex is involved in. For complete graphs, it is N-1 or approx N (there is an edge from each vertex to each of the other vertices).

I corrected the slide.


On Mon, Oct 20, 2008 at 8:21 PM, Mithila Nagendra <> wrote:
Hello Dr. Rao
In the slides for random graphs, there is point where the expected degree k for p=1.0 is given as equal to 1/2N^2. The following slide says that k=N for p=1.0, this makes sense since k=pN. I dont understand how p can also equal 1/2N^2.
Thank you
Mithila Nagendra

No comments: