Trees, Forests and Spanning Trees — Examples

In the case $n\le 3$, connectedness and the edge count force $K_1,K_2,P_3$, respectively.

In the case $n=4$, maximum degree two forces the connected acyclic graph $P_4$, while maximum degree three forces $K_{1,3}$. These degree sequences differ, so the two are nonisomorphic.

In the case $n=5$, maximum degree two gives $P_5$, maximum degree four gives $K_{1,4}$, and maximum degree three forces degree sequence $(3,2,1,1,1)$ by the degree sum $8$.

Each displayed degree sequence determines the indicated tree: attach all remaining vertices to the unique high-degree vertex, with the degree-two vertex extending one arm in the third case.

The representatives in each row have different degree sequences, so they are pairwise nonisomorphic and the list is complete.

Initially the leaves are $0,1,3,4$. Delete $0$ and record $2$; then delete $1$ and record $2$; then delete $3$ and record $2$. Thus the code is $(2,2,2)$.

To decode, the least label absent from $(2,2,2)$ is $0$, so add $02$; for the suffix $(2,2)$ choose $1$ and add $12$; for $(2)$ choose $3$ and add $23$.

The unused labels are then $2,4$, so add $24$. The recovered edge set is exactly $\{02,12,23,24\}$.

Deleting any one edge of $C_n$ gives a connected acyclic spanning graph, hence a spanning tree. The $n$ choices yield distinct trees.

Conversely, every spanning tree uses $n-1$ of the $n$ cycle edges, so it is obtained by deleting exactly one edge.

Therefore $\tau (C_n)=n$.

There are $4$ choices for each of the two positions of a Prüfer word, hence $4^2=16$ words and therefore $16$ spanning trees.

Independently, Cayley's formula gives $\tau (K_4)=4^{4-2}=16$, agreeing with the enumeration.

The graph $T$ is the path $1,2,3,4$, so it is a spanning tree. Its unique $1$-$4$ path together with $14$ is the stated $4$-cycle.

Deleting $23$ leaves vertex sides $\{1,2\}$ and $\{3,4\}$. Exactly $23,13,14$ cross between them in $G$.

Hence the displayed cycle and cut are the required fundamental objects.

Deleting any edge of $C_3$ leaves a two-edge path on all three vertices, so each result is a spanning tree.

The three deleted edges are different, so the three resulting edge sets are distinct. In particular, this connected graph has at least two spanning trees.

Kruskal considers the edges in weight order and accepts $ab$, then $bc$, then $cd$; at that point all four vertices are connected.

From $a$, Prim first chooses $ab$ of weight $1$, then $bc$ of weight $2$, then $cd$ of weight $3$.

Both procedures output the path with total weight $1+2+3=6$, and their correctness theorems make it an MST.

The graph ${\bar{K}}_2$ is acyclic because it has no edges.

Its two vertices lie in different components, so it is disconnected and therefore is not a tree.

Thus acyclicity alone does not imply the tree property.

The disjoint union has $n=4$ vertices and $3=n-1$ edges.

It is disconnected and also contains the cycle $C_3$, so it is not a tree.

Hence the edge count alone is insufficient.

Each of the three two-edge spanning trees has total weight $2$.

Every spanning tree of the three-vertex graph has two edges, so no spanning tree has smaller weight.

Thus all three are MSTs, and uniqueness fails.

At $n=4$, Cayley's number is $4^{4-2}=16$.

The unlabelled count is $2$.

Since $16\mathrm{\ne }2$, Cayley's formula does not count unlabelled isomorphism types.

In $C_3$, fix an edge $e$ and delete it. The remaining two edges form a spanning tree.

This spanning tree omits $e$; adding $e$ back closes the triangle as its fundamental cycle.

Hence an edge of a connected graph need not lie in every spanning tree.