Graph Theory - Trees

This post is second in a series of compendium-style posts, intended as an encyclopaedic collection all of the useful properties of a certain class of objects relevant to one of my courses (in this case, graph theory). I realise that this posts are slightly unappealing to read, but they constitute excellent revision.

Today, I'm interested in trees.

Definition. The following give equivalent conditions for a graph $G$ to be a tree:

1. $G$ is connected and acyclic.
2. $G$ is minimally connected.
3. $G$ is maximally acyclic. 
4. $G$ is connected with $e(G)=n-1$.
5. $G$ is acyclic with $e(G)=n-1$.

At first, we start with the first definition. Equivalence of 1,2 and 3 are established via follow-your-nose contradiction arguments. Equivalence of 1, 4 and 5 will come later.

A (finite) graph is connected $\Leftrightarrow$ it contains a spanning tree.

A minimally connected subgraph of $G$ gives a spanning tree. Conversely, a spanning tree is obviously connected, and the supergraph of a connected graph is connected.

Every tree $T$ with $|T|\geq 2$ has at least two leaves.

A leaf is a vertex with exactly one neighbour.

Pick a vertex $x_1$. Consider a maximal path from $x_1$, say $x_1x_2\ldots x_k$. Let $y$ be a neighbour of $x_k$, $y \neq x_{k-1}$. If $y$ is in the path, we have found a cycle. If $y$ is not in the path, we can extend the path to $x_1x_2\ldots x_k y$, contradicting maximality. So $x_k$ is a leaf. 

Now, repeat this argument, starting from $x_k$, to find a second leaf. 

A tree $T$ of order $n$ has size $n-1$. 

We induct on $n$. The base cases $n=1,2$ are clear. Pick a leaf $v$. Then $T-v$ is connected, acyclic, hence a tree, and so $e(T-v)=n-2$ by the induction hypothesis. 

We can use this to prove equivalence of definitions 1,4 and 5, above. 

(Cayley's theorem) There are $n^{n-2}$ labelled trees of order $n$.

We construct a bijection between labelled trees and strings of length $n-2$ over an alphabet of $n$ letters. (The sequence corresponding to a tree is called its Prufer sequence.)

(Algorithm for tree $\rightarrow$ string)

• Select the lowest labelled leaf, record its neighbour, remove it. 
• Repeat previous step until exactly one edge is left, and stop.

This produces a string of length $n-2$ with values in $\{1,\ldots,n\}$.

(Algorithm for string $\rightarrow$ tree)

• Set all vertices to "unused". 
• Select the smallest "unused" vertex that does not appear in the string, mark it "used", and join it to the vertex labelled with the next value in the string. Delete this vertex from the string.
• Repeat previous step until the string ends.
• Finish off by connecting the last two unused vertices.

None of the steps produces a cycle (when we mark a vertex used, none of the branches "behind" it are ever touched again), and we create $n-1$ edges. Thus, by definition 5 above, we have a tree. 

$(4,4,4,4)$	$(4,6,4,5)$

Sanity check: note that each node appears in the sequence $d(v)-1$ times, where $d(v)$ is its degree.

These processes are inverse to each other, and so we have a bijection. There are $n^{n-2}$ possible strings, and so there are equally many possible labelled graphs. $\square$

Things to think about: Can we obtain a description of the number of isomorphism classes (unlabelled graphs) by thinking about the size of the orbit of $(a_1,a_2,\ldots,a_{n-2})$ under the action of $S_{n-2}$ on the set of Prufer sequences given by $(\sigma(a_1),\sigma(a_2),\ldots,\sigma(a_{n-2}))$, for $\sigma \in S_{n-2}$, or is it more complex than that?

Existence of spanning tree $\Leftrightarrow$ Zorn's lemma
Extracurricular result

Assuming Zorn's lemma, every (connected) graph has a spanning tree: consider the set of all subgraphs that are trees, ordered by inclusion. This is obviously chain-complete (the acyclic definition survives unions of chains), and a maximal element corresponds to a spanning tree.

[Proof of the converse omitted currently, as I want to try to come up with a proof myself at some point.]