1
$\begingroup$

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?

1 Answers 1

1

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.