A simple undirected graph has no self-loops and no parallel edges.
For even n, determine how many of the simple undirected graphs $G$ = $(V, E)$ with $V = {1, . . . , n}$ have all vertices of degree $1$.
I know how to find the total number of graphs. But couldn't figure from the given conditions.
Any ideas?
Best Answer
Hint:If all vertices are of degree 1, this is equivalent to a perfect matching in the graph $K_{n}$.
Your condition is not possible with odd $n$. The handshaking lemma is an easy way to show this. The sum of degrees have to be even, and this is not possible with an odd number of $1$'s. We look at the even case $2n$.
In $K_{2n}$, pick an arbitrary vertex $u$, you can match it with $(2n−1)$ vertices. After matching $u$, you are left with $2n−2$ vertices. Repeat this process until you don't have any vertices. You get the relation $a_n=(2n−1)a_{n−1}$. Solving, you get $a_n=(2n−1)(2n−3)\dots(1)$.
Some other forms to this expression are, $a_n=(2n-1)!!=\frac{(2n)!}{2^nn!}$.