# When randomly selecting n unique edges from a complete graph, what is the probability distribution for the numbers of covered vertices?

Assume that we have a complete graph $G = \{V,E\}$, where $V$ is the vertices set and $E$ is the edges set. We randomly select $n$ unique edges from $G$ ($n \le |E|$), and these edges cover $m$ vertices.

The problem is: what is the probability distribution for $m$?

=========================================

==========================================

Now I am trying to transform this problem to picking random element pairs from a set, and I find this post could be helpful since it asked a very similar question. https://stackoverflow.com/questions/15793172/efficiently-generating-unique-pairs-of-integers

Could anyone please help me?

• Please see here. What have you tried? – Nobody Aug 5 '16 at 14:41
• Let $|V|=N$. The first vertice has $N-1$ neighbours, the next $N-2$ (without the first), etc. To choose an edge is like to choose one pair (vertice,neighbour). You need to choose $n$. It seems to be sth like stars and bars – Michael Freimann Aug 5 '16 at 14:59

## 1 Answer

To start with some notation, let's assume $G=(V,E)$ is the complete graph with $N$ vertices. For a subset $X\subset E$, let $V_X$ denote the vertices of $X$. So the question is to find the probability of $|V_X|=m$ for random $X$ of size $n$.

For any set $U\subset V$ of size $m$, we can find the number of sets $X\subset E$ with $V_X=U$ using the inclusion-exclusion principle $$a_{n,m}=\sum_{r=0}^m (-1)^{m-r} \binom{m}{r}\binom{\binom{r}{2}}{n}$$ which corresponds to an alternating sum over sets $X$ and $W$ such that $V_X\subset W\subset U$ with $r=|W|$ in such a way that cases with $V_X=U$ sum to one and all others sum to zero. I've added a more detailed explanation below.

The number of sets $U\subset V$ of size $m$ is $\binom{N}{m}$, so the number of ways to pick $X\subset E$ and $U\subset V$ of sizes $n$ and $m$ is $$A_{n,m}=a_{n,m}\cdot\binom{N}{m} =\sum_{r=0}^m (-1)^{m-r} \binom{N}{m}\binom{m}{r}\binom{\binom{r}{2}}{n}$$ where the total number of ways to pick $X\subset E$ of size $n$ is $$A_n=\sum_m A_{n,m}=\binom{\binom{N}{2}}{n}$$ as expected.

So the probability of getting $|V_X|=m$ for a random $X\subset E$ of size $n$ is $$p_{m|n}=\frac{A_{n,m}}{A_n}.$$

Here's a more detailed explanation of the use of the inclusion-exclusion principle in this particular case.

The problem is that, while you can easily count the number of sets $X\subset E$ with $V_X\subset U$ for any $U\subset V$, but it's harder to only count the $X$ what make $V_X=U$. So what we want to do is to count all $X$ with $V_X\subset U$, and than subtract all those for which $V_X$ is smaller than $U$.

For any $W\subset V$, the number of subsets $X\subset E$ of size $n$ with $V_X\subset W$ is $$A_n(W)=\binom{\binom{|W|}{2}}{n}$$ since there are $\binom{|W|}{2}$ edges between the vertices of $W$.

If we start with $A_n(U)$, we have counted all $X$ with $V_X\subset U$: not only $X$ with $V_X=U$, but also those for which $V_X$ is smaller than $U$. E.g. if $V_X=U\setminus\{u\}$ for some $u$, it is counted in $A_n(U)$. So a first step is to subtract those: $$A_n(U)-\sum_{u\in U}A_n(U\setminus\{u\}).$$ This counts $X$ with $V_X=U$ once, while $X$ with $V_X=U\setminus\{u\}$ for some $u\in U$ are not counted. However, $X$ with $V_X=U\setminus\{u_1,u_2\}$ have been subtracted twice and have to be added back in: $$A_n(U)-\sum_{u\in U}A_n(U\setminus\{u\}) +\sum_{\{u_1,u_2\}\subset U} A_n(U\setminus\{u_1,u_2\}.$$ And so we go on alternatingly adding and subtracting until we get $$\sum_{W\subset U}(-1)^{|U\setminus W|} A_n(W)$$ as the number of $X$ so that $V_X=U$. Now insert that $W\subset U$ with $|W|=r$ can be selected in $\binom{m}{r}$ different ways and $|U\setminus W|=m-r$, and you get the sum for $a_{n,m}$.

• Thanks very much for your kindly help. The answer is precise and clear but I am still trying to understand the part about calculating $a_{m,n}$. I am reading the WIKI page of the "inclusion-exclusion principle", could you please give me a little illustrations of this part? Thank you! – bigorange66 Aug 7 '16 at 11:38
• @bigorange66 Have added an explanation with some extra details. Put it at the end so the main part of the answer remains more concise. – Einar Rødland Aug 7 '16 at 12:24
• Thank you very much! Now I fully understand the idea! However, I find it is difficult to calculate the result when the graph is big. That is, the number of combinations could 'overflow' on my Matlab. I am trying to figure out a way to solve this problem. – bigorange66 Aug 7 '16 at 18:44