2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ You can tell from the answers to this question that there are various meanings of the term "degree of a tree"; you might want to add a definition for that. $\endgroup$ – joriki Jun 15 '16 at 21:11
  • 1
    $\begingroup$ You added the definition of the degree of a vertex -- that's a well-established concept that doesn't require definition; the question uses the concept of the degree of a tree. $\endgroup$ – joriki Jun 15 '16 at 21:22
  • 1
    $\begingroup$ By the way, the title and body contradict each other. In the title the complete graph is of odd degree;in the body the spanning trees are of odd or even degree. $\endgroup$ – joriki Jun 15 '16 at 21:23
  • $\begingroup$ I edited it again, sorry it's late for me. The Task is to determine the vertices of the spanning Trees with odd degree in the graph $K_{10}$ $\endgroup$ – user348058 Jun 15 '16 at 21:45
  • 1
    $\begingroup$ I'm just guessing, but do you want the number of spanning trees in which all vertices have odd degree? \ $\endgroup$ – bof Jun 15 '16 at 22:03
1
$\begingroup$

We solve the case of all degrees being odd, as a tree with all degrees being even would have no leaves, a contradiction. Introduce the labeled combinatorial species of rooted trees with even outdegree. These have odd total degree at all nodes except for the root, which has even outdegree. The species equation is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z} + \mathcal{Z}\times\textsc{SET}_{=2}(\mathcal{T}) + \mathcal{Z}\times\textsc{SET}_{=4}(\mathcal{T}) + \mathcal{Z}\times\textsc{SET}_{=6}(\mathcal{T}) + \cdots.$$

We thus obtain the functional equation

$$T(z) = z \sum_{q\ge 0} \frac{T(z)^{2q}}{(2q)!} = \frac{1}{2} z (\exp(T(z))+\exp(-T(z))).$$

Now observe that an element of the target species $\mathcal{V}$ of unrooted labeled trees with node degree odd is obtained by connecting two elements of $\mathcal{T}$ by an edge between the two roots. In this way we obtain every element of $\mathcal{V}$ exactly $n-1$ times, because we are essentially considering $\mathcal{V}$ with a marked edge / rooted at an edge, so we are after the following coefficient

$$\frac{n!}{2(n-1)} [z^n] T(z)^2.$$

To compute the desired value we use a variant of Lagrange inversion. With $n\ge 2$ we have

$$\frac{n!}{2(n-1)} [z^n] T(z)^2 = \frac{n!}{2(n-1)} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z)^2 dz.$$

We have $$z = \frac{2T(z)}{\exp(T(z))+\exp(-T(z))}$$ so putting $T(z) = w$ we otain

$$z = \frac{2w}{\exp(w)+\exp(-w)} \\ \text{and}\quad dz = \left( \frac{2}{\exp(w)+\exp(-w)} - \frac{2w \times (\exp(w)-\exp(-w))}{(\exp(w)+\exp(-w))^2} \right) dw.$$

This yields for the integral (three pieces, start with first piece)

$$\frac{n!}{2(n-1)} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(\exp(w)+\exp(-w))^{n+1}}{2^{n+1} w^{n+1}} w^2 \frac{2}{\exp(w)+\exp(-w)} \; dw \\ = \frac{n!}{2^{n+1}(n-1)} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{\exp(w)^n (1+\exp(-2w))^n}{w^{n-1}} \; dw.$$

We get

$$[w^{n-2}]\sum_{q=0}^n {n\choose q} \exp((n-2q)w) = \sum_{q=0}^n {n\choose q} \frac{(n-2q)^{n-2}}{(n-2)!}.$$

The second piece yields

$$-\frac{n!}{2(n-1)} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(\exp(w)+\exp(-w))^{n+1}}{2^{n+1} w^{n+1}} w^3 \frac{2\exp(w)}{(\exp(w)+\exp(-w))^2} \; dw \\ = - \frac{n!}{2^{n+1}(n-1)} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{\exp(w)^n (1+\exp(-2w))^{n-1}}{w^{n-2}} \; dw.$$

We get

$$[w^{n-3}]\sum_{q=0}^{n-1} {n-1\choose q} \exp((n-2q)w) = \sum_{q=0}^{n-1} {n-1\choose q} \frac{(n-2q)^{n-3}}{(n-3)!}.$$

The third piece is very similar and we get

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

This finally yields the formula

$$\frac{n!}{2^{n+1} (n-1)} \left(\sum_{q=0}^n {n\choose q} \frac{(n-2q)^{n-2}}{(n-2)!} - \sum_{q=0}^{n-1} {n-1\choose q} \frac{(n-2q)^{n-3}}{(n-3)!} \\ + \sum_{q=0}^{n-1} {n-1\choose q} \frac{(n-2-2q)^{n-3}}{(n-3)!} \right).$$

We thus obtain the following sequence starting at $n=3:$

$$0, 4, 0, 96, 0, 5888, 0, 686080, 0, 130179072, 0, 36590059520, \\ 0, 14290429935616,\ldots $$

which points us to OEIS A007106 where we see that we have the right answer but apparently no better closed form exists.

This computation is very similar to the one at this MSE link.

The Maple code was as follows.

trees_odd :=
proc(n)
option remember;
local ind, d, a, mset, deg, res;

    if n=1 then return 1 fi;

    res := 0;

    for ind from n^(n-2) to 2*n^(n-2)-1 do
        d := convert(ind, base, n);
        a := [seq(d[q]+1, q=1..n-2)];

        mset := convert(a, `multiset`);
        deg := map(ent -> ent[2]+1, mset);

        if nops(select(q -> type(q, `odd`), deg))
        = nops(deg) then
            res := res + 1;
        fi;
    od;

    res;
end;


X :=
proc(n)
    local fromtsq;

    fromtsq :=
    add(binomial(n,q)*(n-2*q)^(n-2)/(n-2)!, q=0..n)
    - add(binomial(n-1,q)*(n-2*q)^(n-3)/(n-3)!, q=0..n-1)
    + add(binomial(n-1,q)*(n-2-2*q)^(n-3)/(n-3)!, q=0..n-1);

    fromtsq*n!/2^(n+1)/(n-1);
end;

stirling2even :=
proc(n, k)
    n!*coeftayl(coeftayl(exp(-u+u*1/2*(exp(z)+exp(-z))), u=0, k),
                z=0, n);
end;

stirling2evenA :=
proc(n, k)
    (-1)^(n+k)*k!/2^k*
    add(binomial(n,q)*(-1)^q
        * stirling2(q,k) * stirling2(n-q,k), q=1..n-1);
end;

X2 :=
proc(n)
    add(binomial(n, k)*stirling2evenA(n-2, k)*k!, k=1..n);
end;

X3 :=
proc(n)
    add(binomial(n,k)*(-1)^(n+k)*(k!)^2/2^k*
        add(binomial(n-2,q)*(-1)^q
            * stirling2(q,k) * stirling2(n-2-q,k), q=1..n-3),
        k=1..n);
end;

Addendum. We can skip the trees alltogether and work directly with the 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 $$\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 = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+1}} (1-\exp(-z))^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(-z)^{n-q+1}} (1-\exp(z))^k \times (-1) \times \; dz \\ = (-1)^{k+n-q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+1}} (\exp(z)-1)^k \; dz \\ = (-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}.}$$

Another closely related computation appeared at this MSE link.

The Lagrange inversion may be simplified as shown e.g. at this MSE link.

$\endgroup$
0
$\begingroup$

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:

  1. 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$.
  2. 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$.
  3. Repeat until we have $s_{1}$, $\ldots,$ $s_{n-2}$ each adjacent to $t_{1}$, $\ldots$, $t_{n-2}$ (respectively).
  4. 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.

$\endgroup$
  • $\begingroup$ You posted the definition of a Pruefer code including the property that vertex degree is one more than the number of times a vertex appears. Your subsequent discussion is a special case of what I have in the addendum for a generic choice of $n,$ where I make use of the same properties of the code. The Stirling numbers represent set partitions into sets of even cardinality. $\endgroup$ – Marko Riedel Feb 12 '18 at 0:23
  • $\begingroup$ @MarkoRiedel I see now, in your addendum. I honestly felt, after your answer included the species equation and Lagrange inversion, that an elementary answer that used results that would be found in an introductory graph theory book would be a good answer for this question (and I did not read your answer through to the end). $\endgroup$ – Morgan Rodgers Feb 12 '18 at 1:00
  • $\begingroup$ This is the issue of whether material that qualifies as enrichment, connecting to subjects that the OP might not have seen before, whether that would qualify as a useful answer or not. I do think that presenting two different closed forms solving the problem for an arbitrary $n$ has a certain merit which is why I don't quite agree on the downvote. In fact the technique where we extract coefficients using complex variables is a classic in combinatorics and very useful to know. What the reader sees here applies to all sorts of tree functions with functional equations that are like the one above. $\endgroup$ – Marko Riedel Feb 12 '18 at 1:17
  • $\begingroup$ @MarkoRiedel I would guess that someone asking this question would need to dedicate years of study to understand your answer. That does not mean that the techniques aren't useful, but it is like cracking a walnut with a sledgehammer. I didn't intend my vote to be taken personally, if I had considered the context of no other votes of any kind I probably would have withheld it. $\endgroup$ – Morgan Rodgers Feb 12 '18 at 2:11
  • $\begingroup$ In my opinion the material that I posted does not need more than an introductory course in complex variables and another one in combinatorics. Analytic Combinatorics, which is the canonical text by P. Flajolet and R. Sedgewick, has these techniques in the introductory chapters. The latter text will indeed reward years of study. On the other hand I would describe what I presented above as a preliminary example. Thank you for taking the time to explain your vote. $\endgroup$ – Marko Riedel Feb 12 '18 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.