Trees

Let $T_1$ have vertices $\{1, \ldots, 6\}$ and edges $12, 13, 24, 25, 36$. It has $n = 6$ vertices and $5 = n - 1$ edges. Tracing from vertex $1$ reaches $2$ and $3$ directly, then $4, 5$ through $2$ and $6$ through $3$ — all six vertices, so $T_1$ is connected. With $5$ edges already forced to be exactly enough to connect $6$ vertices, no edge is free to close a cycle; indeed the unique path from $4$ to $6$ is $4\text{-}2\text{-}1\text{-}3\text{-}6$, with no alternative route. So $T_1$ is a tree.

Add the edge $45$ to $T_1$, joining two vertices that were not adjacent. Now there are $6$ edges on $6$ vertices — one too many to stay acyclic — and indeed $2, 4, 5$ now form a cycle: $2\text{-}4$, $4\text{-}5$, $5\text{-}2$ are all edges. Every degree outside $\{4, 5\}$ is unchanged; $4$ and $5$ each gain the new edge, going from degree $1$ to degree $2$. This is the last equivalence above in action: in a tree, joining any two non-adjacent vertices creates exactly one cycle, running along the old tree-path between them.

On vertices $\{1, \ldots, 7\}$, take edges $12, 23, 13$ (a triangle) together with $45, 56, 67$ (a path). That is $6 = 7 - 1$ edges — the right count for a tree — but vertex $1$ can never reach vertex $4$: the graph splits into two pieces. So having $n - 1$ edges is not enough on its own; this graph is acyclic nowhere near enough (it has the triangle) and disconnected, failing BOTH halves of the equivalence at once. A real test must check connectivity and the edge count together (or acyclicity and the edge count together).

Let $T_2$ have vertices $\{1, \ldots, 7\}$ and edges $12, 23, 24, 15, 56, 57$. That is $6 = 7 - 1$ edges. Degrees: $\deg(1) = 2$, $\deg(2) = 3$, $\deg(5) = 3$, and $\deg(3) = \deg(4) = \deg(6) = \deg(7) = 1$. The sum is $2 + 3 + 3 + 1 + 1 + 1 + 1 = 12 = 2(7 - 1)$, confirming the handshake count, and $T_2$ has four leaves, $3, 4, 6, 7$ — more than the minimum of two, which the lemma only guarantees as a floor.

A tree has $10$ leaves, and every one of its other vertices has degree exactly $3$. How many vertices does it have? Let $k$ be the number of degree-$3$ vertices, so $n = 10 + k$ and the number of edges is $n - 1 = 9 + k$. The handshake lemma gives $2(9 + k) = 10\cdot1 + k\cdot3$, i.e. $18 + 2k = 10 + 3k$, so $k = 8$ and $n = \mathbf{18}$. Check: $18$ vertices give $17$ edges and degree sum $34$; directly, $10(1) + 8(3) = 10 + 24 = 34$ as well.

Is $(3, 2, 2, 1, 1, 1)$ the degree sequence of some tree on $6$ vertices? Its sum is $3 + 2 + 2 + 1 + 1 + 1 = 10 = 2(6 - 1)$, so the handshake count is right, and every value is at least $1$. Build one: attach two leaves $d, e$ to a hub $a$ (giving $a$ degree $2$ so far), then chain $a\text{-}b\text{-}c\text{-}f$ through degree-$2$ vertices $b, c$ to a last leaf $f$, and finish with $a\text{-}b$ to bring $a$ to degree $3$. The edges are $da, ea, ab, bc, cf$ — $5 = 6 - 1$ of them — with degrees $\deg(a) = 3$, $\deg(b) = \deg(c) = 2$, $\deg(d) = \deg(e) = \deg(f) = 1$, matching the sequence exactly.

Let $G_3$ have vertices $\{1, 2, 3, 4\}$ and edges $12, 23, 34, 41, 13$ — a $4$-cycle with one diagonal, $5$ edges on $4$ vertices, so its circuit rank is $5 - 3 = 2$. Edge $13$ lies on the triangle $1\text{-}2\text{-}3$, so remove it; edge $41$ now lies on the remaining cycle $1\text{-}2\text{-}3\text{-}4\text{-}1$, so remove it too. What is left, $12, 23, 34$, is connected (it is the path $1\text{-}2\text{-}3\text{-}4$) and has $3 = 4 - 1$ edges: a spanning tree, reached by removing exactly the circuit rank's $2$ edges.

How many different spanning trees does $G_3$ (above) have? Any spanning tree uses $3$ of its $5$ edges. Split on the diagonal $13$: if a tree uses $13$, it still needs to reach $2$ (via $12$ or $23$) and $4$ (via $34$ or $41$) — $2 \times 2 = 4$ choices, all acyclic since each just attaches a pendant to edge $13$. If a tree avoids $13$, it must use $3$ of the $4$ remaining cycle edges $12, 23, 34, 41$; removing any one of the four from that $4$-cycle leaves a spanning path, giving $4$ more trees. In total $G_3$ has $4 + 4 = \mathbf{8}$ spanning trees.

Find the Prufer code of the path $1\text{-}2\text{-}3\text{-}4\text{-}5$. The leaves are $1$ and $5$; the lower one, $1$, has neighbor $2$, so record $2$ and delete $1$. Now $2$ is a leaf of what remains ($2\text{-}3\text{-}4\text{-}5$); record its neighbor $3$, delete $2$. Then $3$ is a leaf of $3\text{-}4\text{-}5$; record $4$, delete $3$. Two vertices, $4$ and $5$, remain, so the code is $(2, 3, 4)$ — the pattern for any path $1\text{-}2\text{-}\cdots\text{-}n$ is simply $(2, 3, \ldots, n - 1)$.

Recall $T_2$ from Leaves and Edge Counts: vertices $\{1,\ldots,7\}$, edges $12, 23, 24, 15, 56, 57$, leaves $3,4,6,7$. Lowest leaf $3$ has neighbor $2$: record $2$, delete $3$. Now $4$ is the lowest leaf, neighbor $2$: record $2$, delete $4$ — this drops $2$ to degree $1$, making it a leaf itself. Lowest leaf is now $2$, neighbor $1$: record $1$, delete $2$, which drops $1$ to degree $1$. Lowest leaf is $1$, neighbor $5$: record $5$, delete $1$. Only $6, 7$ are leaves of $5\text{-}6, 5\text{-}7$; lowest is $6$, neighbor $5$: record $5$, delete $6$, leaving just $5, 7$. The code is $(2, 2, 1, 5, 5)$, length $5 = 7 - 2$ as required.

Which tree on $\{1, \ldots, 5\}$ has Prufer code $(3, 3, 2)$? Start every vertex's working degree at $1$ plus its count in the code: $3$ appears twice and $2$ once, so working degrees are $1, 1, 3, 1, 1$ for $1, 2, 3, 4, 5$, making $1, 4, 5$ the leaves. Process the code left to right, always pairing with the smallest current leaf: the first $3$ pairs with leaf $1$ (edge $13$), dropping $3$ to degree $2$; the second $3$ pairs with the next smallest leaf, $4$ (edge $34$), dropping $3$ to degree $1$ — so $3$ itself becomes a leaf; the last entry, $2$, now pairs with the smallest leaf, which is $3$ (edge $23$), dropping $2$ to degree $1$. Two vertices are left unpaired, $2$ and $5$, so close with edge $25$. The tree is $13, 34, 23, 25$ — four edges on five vertices, as required.

Every vertex of $K_4$ has degree $3$ and is adjacent to the other three, so $L = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{pmatrix}$. Deleting the last row and column leaves $L_0 = \begin{pmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{pmatrix}$, with $\det(L_0) = 3(9 - 1) - (-1)(-3 - 1) + (-1)(1 + 3) = 24 - 4 - 4 = 16$. This matches Cayleys Formula exactly, since every labeled tree on $4$ vertices is a subgraph of the complete graph $K_4$: $4^{4-2} = 16$.

Recall $G_3$ (vertices $\{1,2,3,4\}$, edges $12, 23, 34, 41, 13$) from Spanning Trees, where direct case-counting found $8$ spanning trees. Its degrees are $\deg(1)=\deg(3)=3$, $\deg(2)=\deg(4)=2$, giving $L = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -1 & 0 & -1 & 2 \end{pmatrix}$. Deleting row/column $4$ leaves $L_0 = \begin{pmatrix} 3 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 3 \end{pmatrix}$, and $\det(L_0) = 3(6-1) - (-1)(-3-1) + (-1)(1+2) = 15 - 4 - 3 = 8$ — agreeing with the case count, now from a completely different method.

How many spanning trees does the complete bipartite graph $K_{2,3}$ have (parts $\{1,2\}$ and $\{3,4,5\}$, all $6$ cross edges present)? Vertices $1,2$ have degree $3$; vertices $3,4,5$ have degree $2$. The Laplacian is $L = \begin{pmatrix} 3 & 0 & -1 & -1 & -1 \\ 0 & 3 & -1 & -1 & -1 \\ -1 & -1 & 2 & 0 & 0 \\ -1 & -1 & 0 & 2 & 0 \\ -1 & -1 & 0 & 0 & 2 \end{pmatrix}$, and deleting the last row and column gives a $4\times4$ determinant equal to $12$. This matches the general formula for complete bipartite graphs, $m^{n-1}n^{m-1}$ spanning trees for $K_{m,n}$: with $m=2, n=3$, $2^{3-1}\cdot3^{2-1} = 4\cdot3 = 12$.