Spanning trees of $K_{10}$ having all vertices of odd degree.

Question

It is known that the Complete Graph $K_n$ has $n^{n-2}$ spanning trees. The $K_{10}$ has $10^8$ spanning Trees. Now my question: How can I compute the number of spanning Trees with all vertices having odd degree?

Answer 1

This can be done with the symbolic method as shown at this MSE link. We obtained the closed form

$$\frac{1}{2^n}\sum_{q=0}^n {n\choose q} (n-2q)^{n-2}$$

which is zero when $n$ is odd. We can also work directly with Pruefer codes. The degree of a node from a Pruefer code is one more than the number of times it appears in the code. Therefore for the degrees all odd we must count the number of Pruefer codes where all nodes that are present appear an even number of times. This means we partition the distinct slots of the code into $k$ subsets of even size, choose $k$ nodes and fill the slots with one of $k!$ matching permutations. We thus obtain

$$ \sum_{k=1}^n {n\choose k} \times k! \times {n-2\brace k}_{\mathrm{even}}.$$

Here we have

$${n\brace k}_{\mathrm{even}} = n! [z^n] [u^k] \exp(-u+u(\exp(z)+\exp(-z))/2).$$

The combinatorial class is $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET} (\textsc{SET}_{\mathrm{even},\ge 1}(\mathcal{Z})).$$

Extracting the coefficients we have

$${n\brace k}_{\mathrm{even}} = n! [z^n] \frac{(\exp(z)+\exp(-z)-2)^k}{2^k \times k!} \\ = n! [z^n] \frac{(\exp(z)-1)^k(1-\exp(-z))^k}{2^k \times k!} \\ = \frac{n!}{2^k \times k!} \sum_{q=1}^{n-1} \ [z^q] (\exp(z)-1)^k [z^{n-q}] (1-\exp(-z))^k.$$

Now we have

$$[z^q] (\exp(z)-1)^k = \frac{k!}{q!} {q\brace k}.$$

Furthermore

$$[z^{n-q}] (1-\exp(-z))^k = (-1)^{n-q} [z^{n-q}] (1-\exp(z))^k \\ = (-1)^{k+n-q} [z^{n-q}] (\exp(z)-1)^k = (-1)^{k+n-q} \frac{k!}{(n-q)!} {n-q\brace k}.$$

It follows that

$${n\brace k}_{\mathrm{even}} = (-1)^{k+n} \frac{k!}{2^k} \sum_{q=1}^{n-1} {n\choose q} (-1)^q {q\brace k} {n-q\brace k}.$$

We thus obtain the following closed formula for the number of labeled unrooted trees of odd vertex degree:

$$\bbox[5px,border:2px solid #00A000] {\sum_{k=1}^n {n\choose k} (-1)^{k+n} \frac{(k!)^2}{2^k} \sum_{q=1}^{n-3} {n-2\choose q} (-1)^q {q\brace k} {n-2-q\brace k}.}$$