Spanning trees of $K_{10}$ having all vertices of odd degree. 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?
 A: 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}.}$$
A: Note that, in the proof of the fact that $K_{n}$ has $n^{n-2}$ spanning trees, there is a one-to-one correspondence between the spanning trees and elements of $N^{n-2}$, where $N = \{1,2,\ldots,n\}$. In particular, we consider $N$ to be the vertex set of $K_{n}$, and then a sequence $(t_{1}, \ldots, t_{n-2})$ in $N^{n-2}$ gives a tree $T$ in the following way:


*

*Take $s_{1}$ to be the smallest element of $N$ not in $(t_{1}, \ldots, t_{n-2})$, we will let $s_{1}$ and $t_{1}$ be adjacent in $T$.

*Take $s_{2}$ to be the smallest element of $N \setminus \{s_{1}\}$ not in $(t_{2}, \ldots, t_{n-2})$, we will let $s_{2}$ and $t_{2}$ be adjacent in $T$.

*Repeat until we have $s_{1}$, $\ldots,$ $s_{n-2}$ each adjacent to $t_{1}$, $\ldots$, $t_{n-2}$ (respectively).

*Then there are exactly two vertices in $N \setminus \{s_{1}, \ldots, s_{n-2}\}$; these two vertices will be adjacent in $T$. This gives a spanning tree. (I'm omitting the actual proof, just giving the construction for the correspondence.)


In this tree $T$, it can be seen that the degree of a vertex $v \in N$ is equal to $1 + m_{v}$, where $m_{v}$ is the number of times $v$ appears in the corresponding sequence. So a tree with all vertices having odd degree is one in which every number in the sequence appears an even number of times.
Now, let $n = 10$, so $N = \{1, \ldots, 10\}$. We want to find the number of sequences in $N^{8}$ such that every number in the sequence appears an even number or times. I will count these based on $|\{t_{1}, \ldots, t_{8}\}| \in \{1,2,3,4\}$.


*

*If $|\{t_{1}, \ldots, t_{8}\}| = 1$, then all of the numbers in the sequence are the same. There are $|N| = 10$ possibilities.

*If $|\{t_{1}, \ldots, t_{8}\}| = 2$, say $\{t_{1}, \ldots, t_{8}\} = \{a,b\}$ with $a \neq b$, then we have either $a$ appearing twice and $b$ appearing 6 times, or $a$ and $b$ each appearing $4$ times. In the first case we have $10\cdot 9 \cdot \binom{8}{2}$ possibilities, and in the second we have $\binom{10}{2}\binom{8}{4}$ possibilities.

*If $|\{t_{1}, \ldots, t_{8}\}| = 3$, we have $\{t_{1}, \ldots, t_{8}\} = \{a,b,c\}$ with $a$ appearing 4 times, and $b$ and $c$ each appearing twice. This gives $10 \cdot \binom{9}{2}\binom{8}{4}\binom{4}{2}$ possibilities.

*If $|\{t_{1}, \ldots, t_{8}\}| = 4$ then we have four numbers each appearing twice in our sequence. This gives $\binom{10}{4}\binom{8}{2}\binom{6}{2}\binom{4}{2}$ possibilities.


We can total all of this up to obtain
$$10 + 10\cdot 9 \cdot \binom{8}{2}+ \binom{10}{2}\binom{8}{4} + 10 \cdot \binom{9}{2}\binom{8}{4}\binom{4}{2} + \binom{10}{4}\binom{8}{2}\binom{6}{2}\binom{4}{2}$$
total trees of odd degree. This adds up to 686080 trees.
