Lecture 36 — Trees

lecture
discrete-math
graph-theory

Trees: connected graphs with no non-trivial circuits. The topics are trivial and non-trivial circuits, circuit-free graphs, the definition of a tree, what happens when an edge is deleted from a tree, and the main theorem: a graph with \(n\) vertices is a tree if and only if it is simple, connected and has \(n - 1\) edges. That theorem together with the Handshake Theorem answers most counting questions about trees, as in the four worked questions. Pre-work: Video 046 (Trees). The definitions, the theorem, vertices of degree 1 and the counting method are collected in [trees]. Walks, trails, circuits and connectedness are in walks-trails-and-circuits, and degree and the Handshake Theorem in graphs.

Trees are the last topic of the course. For exam revision there is a high-level summary of the course topics, and review sessions for the final exam run the following week.

Goals

  1. Understand the definition and properties of trees.
  2. Gain fluency in graph theory proofs.

Trivial and non-trivial circuits

A circuit is a trail \(v_0 e_1 v_1 e_2 \cdots e_n v_n\) with \(v_0 = v_n\): a walk that ends where it starts and never uses an edge twice (walks-trails-and-circuits). Nothing in that definition stops \(n = 0\), so a single vertex on its own is a circuit.

A trivial circuit is a circuit consisting of a single vertex and no edges.
A non-trivial circuit is a circuit that has edges.
A graph is circuit-free if there are no non-trivial circuits.

Every vertex is a trivial circuit, so every graph has circuits. That is why circuit-free asks only about the circuits that have edges.

The smallest non-trivial circuits:

  • A loop. A loop \(e\) at \(v\) gives the circuit \(v\,e\,v\), with one edge.
  • Two multiple edges. If \(e_1\) and \(e_2\) both join \(u\) and \(v\), then \(u\,e_1\,v\,e_2\,u\) is a circuit: it ends where it starts, and its two edges are different.

So a circuit-free graph has no loops and no multiple edges: it is simple.

A circuit can pass through a vertex more than once. Only its edges cannot repeat.

Figure 1: Left: a single vertex is a trivial circuit, a circuit with no edges. The other three are non-trivial circuits. A loop at \(v\) is the circuit \(v,e,v\). Two edges joining \(u\) and \(v\) make the circuit \(u,e_1,v,e_2,u\), which is why a circuit-free graph has no multiple edges. The circuit on the right, \(w,a,b,w,c,d,w\), visits \(w\) twice but uses each of its six edges once, so it is still a circuit.

Trees

Definition. A graph is a tree if and only if it is connected and circuit-free.

A single vertex is a tree: it is connected, and with no edges it has no non-trivial circuit. So is a single edge, and so is one vertex joined to three others. A triangle is connected but is a circuit, so it is not a tree. Two edges with no vertex in common are circuit-free but not connected, so that is not a tree either. And by the last section, every tree is simple.

Figure 2: Left: four trees, a single vertex, a single edge, one vertex joined to three others, and a larger tree with 13 vertices. Each is connected, and none has a circuit with edges. Right: two graphs that are not trees. The triangle is connected but is itself a non-trivial circuit, in red. The two separate edges have no circuit, but there is no walk from one edge to the other, so the graph is not connected.

The 11 trees with 7 vertices

There are 11 essentially different trees with 7 vertices. Essentially different means different in shape, not just in the names of the vertices or in how the tree is drawn. Two graphs are isomorphic when one can be turned into the other by renaming its vertices: there is a way to match the vertices of one with the vertices of the other so that two vertices are joined in the first exactly when the matching vertices are joined in the second. Isomorphic graphs are the same graph with different labels, and count once. If the 7 vertices are named and two trees count as different whenever their edge sets differ, there are far more of them: \(7^5 = 16807\).

Two words for telling trees apart. The distance between two vertices is the fewest edges on a walk from one to the other. The diameter of a tree is the largest distance between two of its vertices. Renaming vertices changes neither the degrees nor the distances, so isomorphic trees have the same degree sequence and the same diameter. Two trees that differ in either one are essentially different.

Figure 3: All 11 trees with 7 vertices, numbered as in the table below and grouped by diameter. In each tree the red edges are one longest line in it, and its number of edges is the diameter: 6 for tree 1, 5 for trees 2 and 3, 4 for trees 4 to 8, 3 for trees 9 and 10, and 2 for the star, tree 11. No two of the 11 are the same tree redrawn. Where two share a degree sequence and a diameter, they differ in how the vertices of degree 3 or more sit, as the table explains.

Tree Shape Degree sequence Diameter Told apart from the others with the same sequence and diameter by
1 7 vertices in a line \(2, 2, 2, 2, 2, 1, 1\) 6
2 6 in a line, one more on the second \(3, 2, 2, 2, 1, 1, 1\) 5 the degree-3 vertex has two neighbours of degree 1
3 6 in a line, one more on the third \(3, 2, 2, 2, 1, 1, 1\) 5 the degree-3 vertex has one neighbour of degree 1
4 5 in a line, a line of two hanging from the middle \(3, 2, 2, 2, 1, 1, 1\) 4
5 5 in a line, two more on the middle \(4, 2, 2, 1, 1, 1, 1\) 4 the degree-4 vertex has two neighbours of degree 1
6 5 in a line, two more on the second \(4, 2, 2, 1, 1, 1, 1\) 4 the degree-4 vertex has three neighbours of degree 1
7 5 in a line, one more on the second and one on the fourth \(3, 3, 2, 1, 1, 1, 1\) 4 the two degree-3 vertices are not joined
8 5 in a line, one more on the second and one on the third \(3, 3, 2, 1, 1, 1, 1\) 4 the two degree-3 vertices are joined
9 two joined vertices, with 2 and 3 more \(4, 3, 1, 1, 1, 1, 1\) 3
10 two joined vertices, with 1 and 4 more \(5, 2, 1, 1, 1, 1, 1\) 3
11 one vertex joined to the other 6 \(6, 1, 1, 1, 1, 1, 1\) 2

Renaming vertices keeps degrees and keeps which vertices are joined, so it also keeps facts like “the degree-3 vertex has two neighbours of degree 1”. So in each tied pair the two trees are different, and all 11 are essentially different. Trees 2, 3 and 4 share a degree sequence too, but tree 4 has diameter 4.

Why there are no others. Take two vertices at the largest distance \(d\) in a tree, and a walk of \(d\) edges between them. A shortest walk never repeats a vertex (cutting out the part between two visits would make it shorter), so this walk is a line of \(d + 1\) different vertices, \(v_0, v_1, \dots, v_d\). Every other vertex hangs off this line, and nothing can hang so far out that two vertices end up more than \(d\) apart. A tree with 7 vertices has diameter between 2 and 6: at most 6, since a line of \(d + 1\) different vertices needs \(d + 1 \leq 7\), and at least 2, since diameter 1 would make every two vertices joined, and a tree with 3 or more vertices would then contain a triangle. Going through the diameters:

  • \(d = 6\). All 7 vertices are on the line: tree 1.
  • \(d = 5\). One vertex is left, joined to \(v_1, v_2, v_3\) or \(v_4\). Joining it to an end would make a longer line. \(v_1\) and \(v_4\) give the same tree by reading the line backwards, and so do \(v_2\) and \(v_3\): trees 2 and 3.
  • \(d = 4\). Two vertices are left, \(x\) and \(y\). If both are joined to the line, they hang off \(v_1, v_2\) or \(v_3\), giving the pairs \(\{v_2, v_2\}\), \(\{v_1, v_1\}\), \(\{v_1, v_3\}\) and \(\{v_1, v_2\}\), up to reading backwards: trees 5, 6, 7 and 8. Otherwise \(y\) hangs off \(x\) and \(x\) off the line, and \(x\) must be on the middle vertex \(v_2\), since on \(v_1\) the vertex \(y\) would be 5 from \(v_4\): tree 4.
  • \(d = 3\). Three vertices are left, and each must be joined to \(v_1\) or \(v_2\) directly: not to an end, which would make a longer line, and not to another hanging vertex, since a vertex two steps out from \(v_1\) is 4 from \(v_3\), and two steps out from \(v_2\) is 4 from \(v_0\). Splitting 3 as \(0 + 3\) or \(1 + 2\) (up to reading backwards) gives trees 10 and 9.
  • \(d = 2\). Every vertex is within 2 of every other: one vertex joined to all six others, tree 11.

That is \(1 + 2 + 5 + 2 + 1 = 11\).

This count, and the next fact, are for interest only and are not assessed. Call a tree homeomorphically irreducible if no vertex has degree 2. There are exactly 10 such trees with 10 vertices. With 7 vertices there are two, trees 9 and 11, the only rows of the table with no 2 in the degree sequence.

Deleting an edge from a tree

Deleting an edge removes that edge and nothing else. Every vertex stays, including the edge’s endpoints.

If any edge is deleted from a tree then the result is a disconnected graph. This disconnected graph consists of two trees.

Figure 4: Deleting the edge \(e\), in red, from the tree \(T\) with 7 vertices and 6 edges. What is left is two trees: \(T_1\), which is \(u\) and the 2 vertices joined to it, and \(T_2\), which is \(v\) and the 3 vertices it can still reach. There is no walk from \(u\) to \(v\) any more, since a shortest such walk together with \(e\) would make a non-trivial circuit in \(T\). The edge counts add up: \(2 + 3 + 1 = 6\).

The proof uses one fact about walks.

Shortcut fact. If there is a walk from \(x\) to \(y\), there is one that visits no vertex twice: take a shortest walk from \(x\) to \(y\). If it visited some vertex twice, cutting out the part between the two visits would leave a shorter walk from \(x\) to \(y\). A walk that visits no vertex twice also uses no edge twice, because the second time it crossed an edge it would arrive at a vertex it had already visited. So it is a trail.

Proof. Let \(T\) be a tree and let \(e\) be an edge of \(T\) with endpoints \(u\) and \(v\). A loop is a non-trivial circuit, so \(e\) is not a loop and \(u \neq v\). Write \(T - e\) for \(T\) with \(e\) deleted.

  1. There is no walk from \(u\) to \(v\) in \(T - e\). Suppose there were. By the shortcut fact there is one that visits no vertex twice, \(u = w_0\, f_1\, w_1\, f_2 \cdots f_k\, w_k = v\), with \(k \geq 1\) since \(u \neq v\). Its edges \(f_1, \dots, f_k\) are all different, and none of them is \(e\). Then \(u\, f_1\, w_1 \cdots f_k\, v\, e\, u\) ends where it starts and uses no edge twice: a non-trivial circuit in \(T\). That contradicts \(T\) being circuit-free. So \(T - e\) is disconnected.
  2. Every vertex can reach \(u\) or \(v\) in \(T - e\). Let \(x\) be a vertex. \(T\) is connected, so by the shortcut fact there is a walk from \(x\) to \(u\) in \(T\) that visits no vertex twice. If it does not use \(e\), it is a walk in \(T - e\). If it does, then since \(u\) is an endpoint of \(e\) and the walk meets \(u\) only at the very end, \(e\) is its last edge, crossed from \(v\) to \(u\). Leaving off that last step gives a walk from \(x\) to \(v\) that does not use \(e\).
  3. Two trees. Let \(T_1\) be the vertices that can reach \(u\) in \(T - e\), and \(T_2\) those that can reach \(v\), each with the edges of \(T - e\) between them. By 2 every vertex is in \(T_1\) or \(T_2\). By 1 no vertex is in both, since a vertex in both would give a walk from \(u\) to \(v\). An edge of \(T - e\) joins two vertices that can reach each other, so both its endpoints are in the same part. So \(T - e\) is exactly \(T_1\) and \(T_2\), with no edge between them. Any two vertices of \(T_1\) can each reach \(u\), so they can reach each other, and every vertex on the way can reach \(u\) too, so the walk stays in \(T_1\). So \(T_1\) is connected, and likewise \(T_2\). A non-trivial circuit in \(T_1\) or \(T_2\) would be one in \(T\), so both are circuit-free. So \(T_1\) and \(T_2\) are trees. \(\square\)

Two things to take into the next section: \(T_1\) contains \(u\) and \(T_2\) contains \(v\), so each has at least one vertex; and every edge of \(T\) except \(e\) is in exactly one of \(T_1\) and \(T_2\).

A tree with \(n\) vertices has \(n - 1\) edges

Theorem. A graph \(G\) with \(n\) vertices is a tree if and only if it is simple, connected and has \(n - 1\) edges.

There are two directions to prove.

(\(\Rightarrow\)) Every tree is simple, connected and has \(n - 1\) edges

A tree is connected by definition, and it is simple because it is circuit-free (above). What is left is the edge count, by strong induction on \(n\).

Let \(P(n)\) be: every tree with \(n\) vertices has \(n - 1\) edges.

Basis, \(n = 1\). A tree with one vertex has no edges: an edge would have to be a loop at that vertex, and a loop is a non-trivial circuit. \(0 = 1 - 1\), so \(P(1)\) holds.

Inductive hypothesis. Let \(k \geq 1\) be an integer, and suppose that every tree with \(p\) vertices, for every \(p\) with \(1 \leq p \leq k\), has \(p - 1\) edges.

Inductive step. Let \(T\) be a tree with \(k + 1\) vertices. Since \(k + 1 \geq 2\), \(T\) has two different vertices, and as \(T\) is connected there is a walk between them. That walk uses an edge, so \(T\) has an edge \(e\). Delete it. By the previous section this leaves two trees, \(T_1\) with \(p\) vertices and \(T_2\) with \(q\) vertices, where \(p, q \geq 1\) and \(p + q = k + 1\). So \(p \leq k\) and \(q \leq k\), and by the inductive hypothesis \(T_1\) has \(p - 1\) edges and \(T_2\) has \(q - 1\). Every edge of \(T\) is \(e\) or is in exactly one of \(T_1\), \(T_2\), so \(T\) has

\[(p - 1) + (q - 1) + 1 = p + q - 1 = (k + 1) - 1 = k\]

edges. So \(P(k + 1)\) holds, and by strong induction \(P(n)\) holds for every integer \(n \geq 1\). \(\square\)

The induction has to be strong because \(p\) and \(q\) can be any sizes from 1 to \(k\), not just \(k\) (strong-induction-and-the-well-ordering-principle).

Figure 5: The inductive step on a tree with 13 vertices. Deleting the red edge \(e\) leaves two trees: \(T_1\) with \(p = 6\) vertices and \(T_2\) with \(q = 7\). Both are smaller than the whole tree, so the inductive hypothesis gives them \(p - 1 = 5\) and \(q - 1 = 6\) edges. Putting \(e\) back gives \(5 + 6 + 1 = 12 = 13 - 1\) edges, which is \((p - 1) + (q - 1) + 1 = p + q - 1\).

(\(\Leftarrow\)) A simple connected graph with \(n - 1\) edges is a tree

This direction is by contradiction, and it needs one more fact.

Lemma. If \(G\) is connected and \(e\) is an edge of a non-trivial circuit in \(G\), then \(G - e\) is still connected.

Proof. Write the circuit as \(v_0\, e_1\, v_1 \cdots e_m\, v_m\) with \(v_0 = v_m\), and say \(e = e_i\), with endpoints \(v_{i-1}\) and \(v_i\). The edges of a circuit are all different, so \(e\) appears in it only once. Going the other way round the circuit,

\[R:\quad v_i\, e_{i+1}\, v_{i+1} \cdots e_m\, v_m = v_0\, e_1\, v_1 \cdots e_{i-1}\, v_{i-1}\]

is a walk from \(v_i\) to \(v_{i-1}\) that uses every edge of the circuit except \(e\). Now let \(x\) and \(y\) be any two vertices. \(G\) is connected, so there is a walk from \(x\) to \(y\) in \(G\). Each time it crosses \(e\) it steps from \(v_{i-1}\) to \(v_i\) or from \(v_i\) to \(v_{i-1}\); replace that step by \(R\) backwards or by \(R\). The result is a walk from \(x\) to \(y\) that does not use \(e\). So \(G - e\) is connected. \(\square\)

(If \(e\) is a loop then \(v_{i-1} = v_i\) and \(R\) is a walk from that vertex back to itself; the same replacement works.)

Figure 6: Deleting an edge of a circuit keeps a graph connected. Left: a connected graph whose four middle vertices form a circuit, and the walk from \(x\) to \(y\) through the edge \(e\). Right: \(e\) is deleted, and the walk goes round the rest of the circuit instead, in red. The left graph has 6 vertices and 6 edges, one more than a tree with 6 vertices. The right graph is connected with no circuit, a tree with \(6 - 1 = 5\) edges.

Proof of (\(\Leftarrow\)). Let \(G\) be a simple connected graph with \(n\) vertices and \(n - 1\) edges, and suppose, for a contradiction, that \(G\) is not a tree. \(G\) is connected, so it is not circuit-free: it has a non-trivial circuit. Delete one edge of that circuit. By the lemma the graph is still connected, and it still has all \(n\) vertices. If it still has a non-trivial circuit, delete an edge of that one, and keep going. Each deletion removes an edge and keeps the graph connected, and \(G\) has only finitely many edges, so this stops, at a graph \(H\) with no non-trivial circuit. \(H\) is connected and circuit-free, so it is a tree with \(n\) vertices. At least one edge was deleted, so \(H\) has at most \(n - 2\) edges. But by (\(\Rightarrow\)), a tree with \(n\) vertices has exactly \(n - 1\) edges. This is a contradiction, so \(G\) is a tree. \(\square\)

Two remarks on the proof.

  • The word simple is never used in (\(\Leftarrow\)). A connected graph with \(n\) vertices and \(n - 1\) edges is already a tree, and so it turns out to be simple.
  • Neither direction uses anything about vertices of degree 1. So the next worked question, which proves a fact about them from this theorem, is not going round in a circle.

Worked: degree 3 or degree 1

Every vertex of a tree with 15 edges has either degree 3 or degree 1. How many vertices of the tree have degree 3?

Answer: 7.

A tree with 15 edges has \(15 + 1 = 16\) vertices, by the theorem. Let \(x\) be the number of vertices of degree 3. Then \(16 - x\) vertices have degree 1.

By the Handshake Theorem (graphs) the degrees add to \(2 \cdot 15 = 30\). The degree sum is \(3 + 3 + \cdots + 3\), \(x\) times, plus \(1 + 1 + \cdots + 1\), \(16 - x\) times:

\[3x + (16 - x) = 30, \qquad 2x = 14, \qquad x = 7.\]

So 7 vertices have degree 3 and 9 have degree 1. Check: \(7 \cdot 3 + 9 \cdot 1 = 30 = 2 \cdot 15\).

The count shows what any such tree must have. One such tree:

Figure 7: A tree with 15 edges in which every vertex has degree 3 or 1. The 7 vertices of degree 3, in red, lie in a line. The two at the ends each have two more vertices of degree 1 joined to them, and the five in between have one each, so there are \(2 + 5 + 2 = 9\) vertices of degree 1. That is 16 vertices and \(6 + 9 = 15\) edges, and the degrees add to \(7 \cdot 3 + 9 \cdot 1 = 30\).

Worked: how many vertices

A tree has two vertices of degree 4, one vertex of degree 2, and all the other vertices have degree 1. How many vertices does the tree have?

Answer: 9.

Three vertices have degree 4 or 2. Let \(x\) be the number of vertices of degree 1, and \(n\) the total number of vertices, so

\[n = x + 3.\]

By the theorem the tree has \(n - 1 = (x + 3) - 1 = x + 2\) edges. By the Handshake Theorem the degrees add to \(2(x + 2)\):

\[2 \cdot 4 + 1 \cdot 2 + x = 2(x + 2), \qquad 10 + x = 2x + 4, \qquad x = 6.\]

So \(n = x + 3 = 9\). Check: the degrees add to \(4 + 4 + 2 + 6 \cdot 1 = 16 = 2 \cdot 8\), and \(8 = 9 - 1\) edges.

Figure 8: A tree with two vertices of degree 4, one of degree 2 and the rest of degree 1. The vertex of degree 2 sits between the two of degree 4, and each of those has three more vertices of degree 1 joined to it. That is \(3 + 6 = 9\) vertices and 8 edges, and the degrees add to \(4 + 4 + 2 + 6 = 16 = 2 \cdot 8\).

Both questions use the same two facts: a tree with \(n\) vertices has \(n - 1\) edges, and the degrees add to twice the number of edges. Naming the unknown count and writing both facts down gives an equation to solve. The method is in trees.

Worked: two vertices of degree 1

Prove that every tree with at least two vertices has at least two vertices of degree 1.

Proof (by contradiction). Suppose there is a tree \(T\) with \(n \geq 2\) vertices that has at most one vertex of degree 1.

By the theorem \(T\) has \(n - 1\) edges, so by the Handshake Theorem

\[\sum_{v \in V(T)} \deg(v) = 2(n - 1) = 2n - 2.\]

Since \(T\) is a tree it is connected, and since it has at least 2 vertices, every vertex has a walk to some other vertex, so no vertex has degree 0. There are two cases.

  • No vertex of degree 1. Then every vertex has degree at least 2, and \(\sum \deg(v) \geq 2n\).
  • Exactly one vertex of degree 1. All the others have degree at least 2, and \(\sum \deg(v) \geq 1 + 2(n - 1) = 2n - 1\).

In either case \(\sum \deg(v) \geq 2n - 1\). But the sum is \(2n - 2\), so \(2n - 2 \geq 2n - 1\), that is \(-2 \geq -1\), which is false. So every tree with at least two vertices has at least two vertices of degree 1. \(\square\)

Both conditions matter. A line of vertices has exactly two vertices of degree 1, its ends, so “two” cannot be improved. And the tree with one vertex has no vertex of degree 1 at all: its only vertex has degree 0. More on vertices of degree 1, including a second proof, is in trees.

Worked: degrees \(n - 2\) and \(n - 3\)

Prove that if there exists a tree with \(n\) vertices that has a vertex of degree \(n - 2\) and another vertex of degree \(n - 3\), then \(n \leq 5\).

Read it as: if any tree with \(n\) vertices has these two degrees, then \(n \leq 5\). The two vertices have different degrees, so they are automatically two different vertices.

Proof (by contradiction). Let \(T\) be a tree with \(n \geq 6\) vertices that has a vertex \(v_1\) of degree \(n - 2\) and a vertex \(v_2\) of degree \(n - 3\).

By the theorem \(T\) has \(n - 1\) edges, so by the Handshake Theorem

\[\sum \deg(v) = 2(n - 1) = 2n - 2.\]

Since \(T\) is connected and has at least 2 vertices, no vertex has degree 0, so every vertex has degree at least 1. Apart from \(v_1\) and \(v_2\) there are \(n - 2\) vertices, and \(n - 2 \geq 4\) since \(n \geq 6\). They contribute at least 1 each, so at least 4 in all:

\[\sum \deg(v) \geq (n - 3) + (n - 2) + 4 = 2n - 5 + 4 = 2n - 1.\]

So \(2n - 2 \geq 2n - 1\), which is false. So \(n \leq 5\). \(\square\)

The same count without contradiction: if such a tree exists then \(n - 3 \geq 0\), so \(n \geq 3\) and every degree is at least 1. Then

\[2n - 2 = \sum \deg(v) \geq (n - 2) + (n - 3) + (n - 2) = 3n - 7,\]

which gives \(n \leq 5\).

The bound is reached. With \(n = 5\), a vertex of degree 3 and a vertex of degree 2: join \(v_1\) to \(v_2\) and to two more vertices, and \(v_2\) to a fifth. With \(n = 4\), a vertex of degree 2 and another of degree 1: four vertices in a line. With \(n = 3\) the second vertex would need degree 0, which no tree with at least two vertices has, and with \(n \leq 2\) the degree \(n - 3\) is negative. So the trees with this property have exactly 4 or 5 vertices.

Figure 9: Trees with a vertex of degree \(n - 2\) and another of degree \(n - 3\), the two in red. Left, \(n = 5\): degrees 3 and 2, and the other three vertices have degree 1. The degrees add to \(3 + 2 + 1 + 1 + 1 = 8 = 2 \cdot 4\). Right, \(n = 4\): four vertices in a line, with degrees 2 and 1 marked. With \(n = 6\) the two red vertices alone would need degrees \(4 + 3 = 7\), the four others at least 4 more, and \(11\) is more than the \(2 \cdot 5 = 10\) a tree with 6 vertices allows.

See also