Trees

definitions
discrete-math
graph-theory

A tree is a connected graph with no non-trivial circuits. Trees are the connected graphs with as few edges as possible, and the circuit-free graphs with as many edges as possible, and the two facts meet in one theorem: a graph with \(n\) vertices is a tree exactly when it is simple, connected and has \(n - 1\) edges. With the Handshake Theorem (graphs) that theorem turns questions about the degrees in a tree into equations. Walks, trails, circuits and connectedness are in walks-trails-and-circuits. First met in 2026-10-29-trees, which has the full proofs and the 11 trees with 7 vertices.

Circuit-free graphs

A circuit is a trail that ends where it starts (walks-trails-and-circuits). A single vertex with no edges counts as one.

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 the definition has to say non-trivial: otherwise no graph would be circuit-free.

Every circuit-free graph is simple. A loop \(e\) at \(v\) is the non-trivial circuit \(v\,e\,v\). Two edges \(e_1 \neq e_2\) joining \(u\) and \(v\) make the non-trivial circuit \(u\,e_1\,v\,e_2\,u\). So a circuit-free graph has neither (graphs).

Trees

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

  • A single vertex is a tree. So is a single edge, and so is a line of vertices.
  • A triangle is not a tree: it is a circuit.
  • Two edges with no vertex in common are not a tree: the graph is not connected.
  • Every tree is simple, since it is circuit-free.

Small trees

Counting trees means counting essentially different ones: two trees count as the same if one becomes the other by renaming its vertices (they are isomorphic). Up to renaming there is 1 tree with each of 1, 2 and 3 vertices, 2 with 4 vertices, 3 with 5, 6 with 6 and 11 with 7. The 11 are drawn and checked in 2026-10-29-trees.

Figure 1: Every tree with 1 to 5 vertices, up to renaming the vertices, each labelled with its degree sequence. With 4 vertices there are two: a line, and one vertex joined to the other three. With 5 there are three: a line, a vertex of degree 3 with one of its branches two long, and one vertex joined to the other four. Each tree with \(n\) vertices has \(n - 1\) edges, and each with at least 2 vertices has at least two vertices of degree 1.

Deleting an edge

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

Say the edge \(e\) joins \(u\) and \(v\). If \(u\) could still reach \(v\) without \(e\), a shortest such route repeats no vertex, and together with \(e\) it would be a non-trivial circuit in the tree. So nothing joins the side of \(u\) to the side of \(v\), and every vertex is on one side or the other, because its route to \(u\) in the tree either avoids \(e\) or ends by crossing \(e\) from \(v\). Each side is connected, and has no circuit since the tree has none, so each side is a tree. The careful proof is in 2026-10-29-trees.

Minimally connected, maximally circuit-free

A tree sits exactly on the line between too few edges and too many.

  • Remove any edge and it is no longer connected. That is the last section. Conversely, a connected graph in which every edge disconnects it when deleted is a tree: if it had a non-trivial circuit, deleting an edge of that circuit would leave it connected, since the rest of the circuit still joins the edge’s two endpoints.
  • Add any edge and it gets a circuit. A new loop is a circuit on its own. A new edge \(f\) joining two different vertices \(x\) and \(y\): the tree is connected, so there is a walk from \(x\) to \(y\), and a shortest one never repeats a vertex, so it is a trail. That trail followed by \(f\) back to \(x\) is a non-trivial circuit. Conversely, a circuit-free graph in which every new edge makes a circuit is connected: if \(x\) could not reach \(y\), add a new edge \(f\) joining them. Any circuit it creates must use \(f\), since the graph had none before, and the rest of that circuit would be a walk from \(y\) to \(x\) in the old graph. So no circuit is created.

Figure 2: A tree with 6 vertices and 5 edges, in the middle. Left: deleting any one edge, here the dashed one, leaves two pieces with no walk between them, so a tree has no edge to spare. Right: adding any edge, here the dashed red one, closes a non-trivial circuit, in red, so a tree has no room for another edge. 5 edges is the only number of edges a tree with 6 vertices can have.

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.

(\(\Rightarrow\)) A tree is connected by definition and simple because it is circuit-free. For the edges, use strong induction on \(n\). One vertex: no edges, since an edge would be a loop, which is a circuit. For a tree \(T\) with \(k + 1 \geq 2\) vertices, delete any edge. That leaves two trees with \(p\) and \(q\) vertices, where \(p + q = k + 1\) and \(1 \leq p, q \leq k\). By the inductive hypothesis they have \(p - 1\) and \(q - 1\) edges, so \(T\) has \((p - 1) + (q - 1) + 1 = p + q - 1 = k\) edges. The induction is strong because \(p\) and \(q\) can be any sizes below \(k + 1\).

(\(\Leftarrow\)) Let \(G\) be simple and connected with \(n\) vertices and \(n - 1\) edges, and suppose it has a non-trivial circuit. Deleting an edge of a circuit keeps a graph connected, because the rest of the circuit still joins that edge’s endpoints. Keep deleting edges of circuits until none is left. The result is connected and circuit-free, a tree with \(n\) vertices and at most \(n - 2\) edges, which contradicts (\(\Rightarrow\)). So \(G\) has no non-trivial circuit, and is a tree.

Both directions written out in full, with the two facts about deleting edges proved, are in 2026-10-29-trees.

Two consequences:

  • Simple is automatic. The proof of (\(\Leftarrow\)) never uses it: any connected graph with \(n\) vertices and \(n - 1\) edges is a tree.
  • Connected is not. A triangle together with one more vertex on its own has 4 vertices and 3 edges, and is not a tree. To use the theorem in the (\(\Leftarrow\)) direction, check connectedness.

Vertices of degree 1

A leaf is a vertex of degree 1.

Leaf is the standard word, and it appears in the practice problems, but results in this course are stated as “vertex of degree 1”. In an exam answer, say “vertex of degree 1”, or define leaf before using it.

Theorem. Every tree with at least two vertices has at least two vertices of degree 1.

Proof (handshake). Let \(T\) have \(n \geq 2\) vertices. It has \(n - 1\) edges, so its degrees add to \(2n - 2\). It is connected with at least two vertices, so no vertex has degree 0. If at most one vertex had degree 1, all the others would have degree at least 2, and the degrees would add to at least \(1 + 2(n - 1) = 2n - 1 > 2n - 2\). \(\square\)

Proof (longest walk). Among the walks in \(T\) that visit no vertex twice, take one with the most edges, \(w_0\, f_1\, w_1 \cdots f_k\, w_k\). \(T\) is connected with at least two vertices, so it has an edge, and \(k \geq 1\). Suppose \(w_0\) had another edge \(f \neq f_1\), joining it to \(x\) (\(f\) is not a loop, since \(T\) is simple). If \(x\) is not on the walk, \(x\, f\, w_0\, f_1 \cdots w_k\) is longer and still visits no vertex twice. If \(x = w_j\), then \(w_0\, f_1 \cdots f_j\, w_j\, f\, w_0\) is a non-trivial circuit: its edges are all different, since \(f \neq f_1\) and no other \(f_i\) meets \(w_0\). Both are impossible, so \(\deg(w_0) = 1\), and likewise \(\deg(w_k) = 1\). \(\square\)

The full proof by contradiction is worked in 2026-10-29-trees.

  • “At least two vertices” is needed. The tree with one vertex has no vertex of degree 1: its only vertex has degree 0.
  • “Two” cannot be improved. A line of vertices has exactly two vertices of degree 1, its ends.

How many vertices of degree 1. Subtract 2 from every degree. In a tree with \(n \geq 2\) vertices the total is \((2n - 2) - 2n = -2\). A vertex of degree 1 gives \(-1\), a vertex of degree 2 gives 0, and every other vertex gives \(\deg(v) - 2 > 0\). So

\[\text{number of vertices of degree 1} \;=\; 2 + \sum_{\deg(v) \geq 3} \big(\deg(v) - 2\big).\]

Every vertex of degree 3 adds one more vertex of degree 1, every vertex of degree 4 adds two, and vertices of degree 2 add nothing. A tree whose other vertices all have degree 2 is a line, with exactly 2.

Counting with the Handshake Theorem

Most questions about trees give some of the degrees and ask for a count. Two facts settle them:

  1. The theorem: a tree with \(n\) vertices has \(n - 1\) edges.
  2. The Handshake Theorem: the degrees add to twice the number of edges, so in a tree they add to \(2(n - 1)\).

The method:

  1. Name the unknown count, \(x\).
  2. Write the number of vertices \(n\) in terms of \(x\).
  3. Write the number of edges as \(n - 1\).
  4. Write the degree sum two ways, from the degrees and as \(2(n - 1)\), and set them equal.
  5. Solve, then check that the degrees add to twice the edges.

Two more facts often finish the job: every vertex of a tree with at least two vertices has degree at least 1, and there are at least two of degree 1.

Worked: degrees 4, 3 and 1

A tree has three vertices of degree 4, two vertices of degree 3, and every other vertex has degree 1. How many vertices does it have?

Let \(x\) be the number of vertices of degree 1. Then \(n = x + 5\), and the tree has \(n - 1 = x + 4\) edges. The degree sum is

\[3 \cdot 4 + 2 \cdot 3 + x = 2(x + 4), \qquad 18 + x = 2x + 8, \qquad x = 10.\]

So the tree has \(n = 15\) vertices. Check: \(12 + 6 + 10 = 28 = 2 \cdot 14\), and \(14 = 15 - 1\). The formula for vertices of degree 1 agrees: \(2 + 3 \cdot (4 - 2) + 2 \cdot (3 - 2) = 10\).

Figure 3: A tree with three vertices of degree 4, in red, two of degree 3, in blue, and every other vertex of degree 1. The red vertices lie in a line, each blue vertex hangs off an end of it, and each of the five has two vertices of degree 1 joined to it. That is \(5 + 10 = 15\) vertices and 14 edges, and the degrees add to \(12 + 6 + 10 = 28 = 2 \cdot 14\).

More worked examples, with figures: 2026-10-29-trees (every degree 3 or 1, with 15 edges) and 2026-10-29-trees (two of degree 4, one of degree 2).

Common mistakes

  • Using \(n - 1\) edges for a graph that is not a tree. The count needs connected and circuit-free. In the other direction, \(n - 1\) edges alone is not enough: a triangle and a separate vertex have 4 vertices and 3 edges.
  • Off by one. \(n\) vertices go with \(n - 1\) edges, so 15 edges means 16 vertices, not 14.
  • Miscounting the vertices. If \(x\) is the number of vertices of degree 1 and three other vertices are named, there are \(x + 3\) vertices, not \(x\).
  • Forgetting why no degree is 0. In a tree with at least two vertices every vertex has degree at least 1 because the tree is connected. Say so: the bounds on the degree sum depend on it.
  • Calling a single vertex a leaf. The one-vertex tree has a vertex of degree 0 and no vertex of degree 1. The two-leaves theorem needs at least two vertices.
  • Deleting an edge from any graph and expecting two pieces. That is true for trees. An edge on a circuit can be deleted without disconnecting anything.
  • Reading “circuit-free” as “no circuits at all”. Every vertex is a trivial circuit. Circuit-free means no circuit with edges.
  • Judging two trees by their degree sequences. Different degree sequences mean different trees, but the same degree sequence does not mean the same tree: with 7 vertices, three different trees all have degrees \(3, 2, 2, 2, 1, 1, 1\) (2026-10-29-trees).

See also