Trees, Forests and Spanning Trees

Suppose every vertex of $F$ has degree greater than one.

Since degrees are natural numbers, $F$ has minimum degree at least two.

Hence $F$ contains a cycle.

This contradicts that $F$ is a forest, so some vertex has degree at most one.

If $|V(F)|=0$, then $|E(F)|=0$ and $c(F)=0$, so the identity holds.

Let $|V(F)|>0$, assume the identity for forests with fewer vertices, and choose a vertex $v$ of degree at most one.

Put $F':=F-v$. It remains a forest, and $V(F)$ is the disjoint union of $V(F')$ and $\{v\}$, so $|V(F)|=|V(F')|+1$.

If $v$ is isolated, then $E(F)=E(F')$, while the component family of $F$ is the disjoint union of the component family of $F'$ and $\{\{v\}\}$. Hence $|E(F)|=|E(F')|$ and $c(F)=c(F')+1$.

If $v$ has degree one, deleting it removes its unique incident edge, so $|E(F)|=|E(F')|+1$. It does not change the number of components: $v$ cannot be an internal vertex of a path between remaining vertices, and its neighbour remains in the same nonempty component after deletion. Thus $c(F)=c(F')$.

In the isolated case, the induction hypothesis gives $|V(F)|=|V(F')|+1=(|E(F')|+c(F'))+1=|E(F)|+c(F)$.

In the degree-one case, the induction hypothesis gives $|V(F)|=|V(F')|+1=(|E(F')|+c(F'))+1=(|E(F')|+1)+c(F')=|E(F)|+c(F)$.

The two possible degrees of $v$ have both been handled, so the identity holds for every forest.

Apply the forest identity to $T$: $n=|E(T)|+1$.

Therefore $|E(T)|=n-1$.

The vertices $u$ and $v$ lie in distinct components of $T-e$: otherwise a $u$-$v$ path in $T-e$ together with $e$ would be a cycle in $T$.

Every vertex $x$ lies in the component of $u$ or the component of $v$. Indeed, take an $x$-$u$ path in $T$; if it avoids $e$ it joins $x$ to $u$ in $T-e$, and if it uses $e$ then its segment from $x$ to $v$ avoids $e$.

Thus $T-e$ has exactly two components.

Each component is connected by definition and contains no cycle because it is a subgraph of the acyclic graph $T$. Hence each component is a tree.

There is a $u$-$v$ path $P$ in $T$, and it is unique: if two distinct such paths existed, their first divergence and next reunion would yield a cycle.

Every cycle in $T+uv$ must contain $uv$, since $T$ itself is acyclic. Removing $uv$ from such a cycle leaves a $u$-$v$ path in $T$.

The path $P$ together with the new edge $uv$ is a cycle in $T+uv$.

By uniqueness in step 1.1, the path obtained in step 1.2 is $P$. Hence the cycle in step 2.1 is the only cycle.

If $G$ is a tree, connectedness supplies a path between each two vertices, and two distinct paths would contain a cycle. Thus condition 1 implies condition 2.

Under condition 2, $G$ is connected. Deleting any edge $uv$ leaves no $u$-$v$ path, because such a path together with $uv$ would give a second path in $G$. Thus condition 2 implies condition 5.

Suppose condition 5 holds. If $G$ contained a cycle, deleting one edge of that cycle would leave its endpoints joined around the rest of the cycle and would not disconnect $G$. Hence $G$ is acyclic and therefore is a tree. Thus condition 5 implies condition 1.

Condition 1 implies condition 3 by the tree edge count.

Under condition 3, suppose $G$ had a cycle. Repeatedly delete an edge from a cycle; each deletion preserves connectedness, and finiteness makes the process stop at a connected acyclic spanning graph $T$. At least one edge was deleted, so $|E(T)|<|V(G)|-1$, while the forest identity with one component gives $|E(T)|=|V(G)|-1$, a contradiction. Hence condition 3 implies condition 1.

Under condition 4, the forest identity gives $|V|=(|V|-1)+c$, so $c=1$ and $G$ is a tree. Conversely condition 1 implies condition 4 by definition and the tree edge count.

Condition 1 implies condition 6 by edge addition.

Under condition 6, if $G$ were disconnected, vertices in different components would be nonadjacent and adding an edge between them could create no cycle. Hence $G$ is connected, and its assumed acyclicity makes it a tree.

All six conditions are therefore equivalent.

Choose a path $P=v_0v_1\cdots v_k$ of maximum length. Since $T$ has at least two vertices and is connected, $k\ge1$.

If $v_0$ had a neighbour other than $v_1$, that neighbour could not already lie on $P$, since that would form a cycle; adjoining it would therefore lengthen the maximum-length path $P$. Thus $v_0$ has degree one.

The same argument shows that $v_k$ has degree one.

Since $v_0\ne v_k$, these are two distinct leaves.

For $v\ne r$, its unique root path has positive length and therefore has one vertex immediately before $v$. This vertex is the unique parent of $v$.

Let $uv$ be an edge. The root paths of $u$ and $v$ cannot diverge before their endpoints, since the two divergent tails together with $uv$ would form a cycle. Hence one root path is obtained from the other by appending $uv$.

Their lengths, and therefore their depths, differ by exactly one.

Suppose $F$ is disconnected, and choose vertices $u,v$ in distinct components of $F$.

A $u$-$v$ path in $G$ has a first edge $xy$ whose endpoints lie in distinct components of $F$.

Adding $xy$ to $F$ cannot create a cycle, because a cycle through $xy$ would contain an $x$-$y$ path already in $F$, contrary to the choice of distinct components.

Thus $F+xy$ is a strictly larger acyclic spanning subgraph, contradicting maximality.

Hence $F$ is connected, and therefore it is a spanning tree.

If $G$ is connected, choose a maximal acyclic spanning subgraph $F$; the edgeless spanning subgraph shows that the choice family is nonempty.

By L1, $F$ is a spanning tree of $G$.

Conversely, if $G$ has a spanning tree $T$, every two vertices are joined by a path in $T$, hence by a path in $G$. Thus $G$ is connected.

The endpoints $u,v$ belong to $T$ and are nonadjacent there.

Let $P$ be the unique $u$-$v$ path in $T$. By edge addition, $P+e$ is the unique cycle in $T+e$.

Let $A,B$ be the vertex sets of the two components of $T-e$. They partition $V(G)$.

If $f=xy$ crosses from $A$ to $B$, then $T-e+f$ is connected: paths inside $A$ and $B$, together with $f$, join every pair of vertices.

It is acyclic: each side is acyclic, and a cycle using $f$ would require a second edge between the two sides, but $T-e+f$ has only $f$.

It is spanning by construction, so it is a spanning tree of $G$.

The map sending a spanning tree to its edge set embeds the set of spanning trees into $\mathcal P(E(G))$.

The latter power set is finite, so its subset consisting of spanning-tree edge sets is finite.

Before any word entry is processed, the graph has $n$ singleton components indexed by $S$, each containing exactly one unused label.

Assume that after $i$ stages the built edges form a forest and every component contains exactly one unused label.

There are $n-i$ unused labels and $n-2-i$ entries in the remaining word. Hence at least two unused labels are absent from that word, so the least such label $v$ exists. Every label used at an earlier stage was absent from the then-remaining word and hence from its current suffix, so $a_i$ is unused; because $a_i$ occurs in the remaining word, $v\ne a_i$.

The label $a_i$ lies in a component different from the component containing $v$: by the induction hypothesis each component contains exactly one unused label, and $a_i\ne v$. Adding $va_i$ and marking $v$ used joins those components without a cycle and leaves exactly one unused label in the new component. Thus the invariant holds after stage $i+1$.

Induction gives the invariant after all $n-2$ word stages. Exactly two unused labels and two components remain; joining those labels makes the graph connected without creating a cycle.

The output uses all labels in $S$ and is connected and acyclic, hence is a labelled tree on $S$.

On a two-element natural-label set, the only word is empty and the only tree is the edge joining the labels, so encoding and decoding agree.

Assume that encoding and decoding are inverse on every finite natural-label set of size $n-1$.

Let $w=a_0\cdots a_{n-3}$ and let $v$ be the least label absent from $w$. Decoding first attaches $v$ to $a_0$ and never uses $v$ again.

Conversely, let $T$ be a labelled tree, let its first encoding operation delete the least leaf $u$, and let it record the neighbour $b$.

In the decoded tree, $v$ is a leaf. Every label smaller than $v$ occurs in $w$, so while it is unused it receives an edge as a recorded neighbour and later receives its deletion edge or the final edge. Hence no smaller label is initially a leaf, and encoding first deletes $v$ and records $a_0$.

The label $u$ is absent from the full code. Every smaller label is not initially a leaf, so before it can be deleted, deletion of an incident leaf records it at least once. Thus $u$ is the least label absent from the code, and decoding first restores the edge $ub$.

After removing $v$ and the first word entry, both procedures operate on the same ordered label set of size $n-1$ and the suffix word. The induction hypothesis shows that the remaining operations are inverse. Thus encoding the decoded tree returns $w$.

After deleting $u$ and the first code entry, the induction hypothesis restores the remaining tree on its ordered label set of size $n-1$. Therefore decoding the code of $T$ returns $T$.

Both composites are identities, so encoding and decoding are inverse bijections on the ordered label set of size $n$. Applying this to the natural order on $n$ proves the theorem.

For $n\ge2$, spanning trees of $K_n$ are exactly the trees on its fixed label set.

By the Prüfer bijection, they correspond to functions from an $(n-2)$-element position set to $n$, of which there are $n^{n-2}$.

The sole spanning tree of $K_1$ is $K_1$ itself, so $\tau(K_1)=1$. The null graph $K_0$ is not a tree and has no spanning tree, so $\tau(K_0)=0$.

Construct $T':=T-f+e$, where $e\notin E(T)$ and $f\ne e$ lies on the fundamental cycle of $e$. Removing $f$ breaks that cycle but leaves the graph connected, because the rest of the cycle replaces every use of $f$.

No other cycle exists in $T+e$, so $T-f+e$ is connected, acyclic and spanning, hence a spanning tree.

The second assertion is exactly the restoration clause for the fundamental cut of $f$.

Let $e$ be a minimum edge crossing a cut and choose an MST $T$. If $e\in T$, this MST already proves assertion 1. If $e\notin T$, the fundamental cycle of $e$ contains a tree edge $f$ crossing the same cut.

Let $g$ be a maximum edge on a cycle and choose an MST $S$. If $g\notin S$, this MST already proves assertion 3. If $g\in S$, deleting $g$ gives a fundamental cut, and the remainder of the cycle contains an edge $h$ crossing that cut.

In the second case of step 1.1, $w(e)\le w(f)$, so $T-f+e$ is an MST containing $e$. Together with the first case, this proves assertion 1.

If $e$ is uniquely minimum across the cut and an MST omitted it, the same exchange would have $w(e)<w(f)$ and strictly decrease total weight. Thus every MST contains $e$.

In the second case of step 1.2, $w(h)\le w(g)$, so $S-g+h$ is an MST omitting $g$. Together with the first case, this proves assertion 3.

If $g$ is uniquely maximum on the cycle, then $w(h)<w(g)$ in step 1.2, so no MST can contain $g$.

Suppose $T$ and $T'$ are distinct MSTs. Choose the least-weight edge $e$ in the symmetric difference $E(T)\mathbin\triangle E(T')$, and assume after swapping names that $e\in E(T)\setminus E(T')$.

By [L3], $T'+e$ has a fundamental cycle. Apart from $e$, that cycle cannot consist entirely of edges of $T$, since then it would be a cycle in $T$. Hence it contains an edge $f\in E(T')\setminus E(T)$.

The choice of $e$ and distinct weights gives $w(e)<w(f)$.

The exchange $T'-f+e$ is a spanning tree of weight $w(T')-w(f)+w(e)<w(T')$, contradicting the minimality of $T'$.

Hence the MST is unique.

Maintain the invariant that the current forest $F$ is contained in some MST. It holds initially by L1.

Suppose $F\subseteq T$ for an MST $T$, and Kruskal chooses $e$. If $e\in T$, the invariant persists.

If $e\notin T$, let $C$ be its fundamental cycle in $T+e$. Some edge $f\in E(C)\setminus\{e\}$ is not in $F$; otherwise the $T$-path $C-e$ would lie in $F$ and adding $e$ to $F$ would create a cycle. Since $F+f$ is a subgraph of the acyclic tree $T$, the edge $f$ is eligible for Kruskal.

At the moment $e$ is chosen, $f$ is eligible, so $w(e)\le w(f)$. The exchange $T-f+e$ is a spanning tree of no greater weight, hence an MST containing $F+e$.

Thus the invariant holds after every choice.

On termination, $F$ must be connected: otherwise a path of $G$ between two components of $F$ would contain a first edge joining distinct components, and that edge would still be eligible. Thus $F$ is a spanning tree. The invariant then forces $F$ itself to be an MST.

Therefore every tie-breaking execution returns a minimum spanning tree.

Maintain the invariant that the chosen edges $F$ are contained in some MST. It holds for $F=\varnothing$ by L1.

Assume the invariant for the current reached set $S$. If $S$ is not all of $V(G)$, connectedness gives an edge crossing $(S,V(G)\setminus S)$, so a minimum-weight crossing edge $e$ exists.

Choose an MST $T$ containing $F$. If $e\notin T$, the $T$-path between the endpoints of $e$ contains an edge $f$ crossing $(S,V(G)\setminus S)$. No edge of $F$ crosses this cut, and $w(e)\le w(f)$, so $T-f+e$ is an MST containing $F+e$. Thus in either case some MST contains $F+e$.

Hence the invariant persists, and adding $e$ reaches one new vertex without creating a cycle.

After all vertices are reached, $F$ is connected and acyclic with all vertices, so it is a spanning tree. Since an MST contains all its edges, it equals $F$.

Thus Prim's procedure returns an MST for every permitted tie-breaking.