Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A random graph consisting of n vertices and k undirected edges is constructed by repeating the following step k times:

Randomly choose 2 vertices without replacement from n vertices, and connect them with an edge.

What is the expected degree of a vertex?

I know that expected value is calculated by the probability*degree, but I'm not sure how to make a general case when we have n vertices and k undirected edges. Can someone make this problem easier to understand by explaining how the expected value is related to the problem statement? How can I generalize other problems of the same form?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The expected degree of a vertex doesn't actually depend on the details of the procedure as long as it doesn't distinguish between the vertices. It's not clear to me whether by "without replacement" you mean that the two vertices are never chosen again individually or only that this pair of vertices is never chosen again as a pair, but it doesn't matter because as long as the vertices are all treated the same the expected degree of a vertex must equal the average degree of a vertex, which is simply $2k/n$, since there are $2k$ incidences and $n$ vertices.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.