Back to the on-screen lesson ·
Connected and acyclic, the edge count that follows, the four equivalent descriptions, and the spanning tree inside every connected graph.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to decide whether a graph is a tree by counting its edges and checking connectivity, use the fact that a tree on n vertices has n minus one edges together with the handshake lemma to answer questions about degrees and leaves, and build a spanning tree inside any connected graph. You will also be able to follow the induction that proves the edge count, including the lemma it needs — that every finite tree with an edge has a leaf — which the statement itself never mentions.
Lesson 20 gave the handshake lemma and the vocabulary of walks, paths and connectivity. Lesson 10 gave induction. This lesson is those two together: the one theorem it proves is an induction on the number of vertices, and the arithmetic it uses afterwards is the handshake lemma.
A graph is acyclic when it contains no cycle. A tree is a connected acyclic graph; a forest is an acyclic graph, connected or not. A leaf is a vertex of degree one. A spanning tree of a connected graph is a tree inside it that reaches every vertex.
The theorem. A tree with $n$ vertices has exactly $n - 1$ edges.
The quick way to see it: grow the tree one vertex at a time. The first vertex brings no edge, and every later one arrives on exactly one — more would close a cycle, fewer would leave it stranded. So $n$ vertices bring $n-1$ edges.
That is a fine explanation and not quite a proof, because an arbitrary tree does not come with a history of how it was built. The proof runs the other way, by induction, removing a leaf: if every tree on $k$ vertices has $k-1$ edges, take a tree on $k+1$, delete a leaf and its edge, apply the hypothesis, and put the edge back.
That needs a lemma the theorem never mentions: every finite tree with an edge has a leaf. If every vertex had degree at least two, start walking and never reuse an edge; the graph is finite, so a vertex must repeat, and that closes a cycle. Noticing that the step needs something the statement does not mention is normal for an induction on a graph, and it is where these proofs are actually hard.
Four equivalent descriptions. For a graph with $n$ vertices, these say the same thing:
A theorem stating that several conditions are equivalent is proved as a ring of implications, which is lesson 1's transfer question arriving with a real example: four implications rather than twelve.
Spanning trees. Every connected graph contains one, found by growing outwards and refusing any edge whose two ends are already connected. It is the cheapest network that keeps everything reachable, which is why the idea is everywhere outside mathematics as well as in it.
Another way: steps
To decide whether a graph is a tree:
Another way: picture
A path, a star and a caterpillar, all on seven vertices. They look nothing alike and every one of them has six edges. The edge count is forced by the vertex count; the shape, and with it the number of leaves, is not.
The two facts combine constantly. A tree on $n$ vertices has $n-1$ edges, so its degrees add to $2n-2$ — a total fixed before anything is known about its shape.
That gives quick answers to questions that look as though they need the picture. A tree has $12$ vertices, $5$ of them leaves. What do the other degrees add to? Total $22$; the leaves contribute $5$; the rest contribute $17$.
Or: how many leaves must a tree on $n \ge 2$ vertices have? At least two. If it had at most one, the degrees would add to at least $2(n-1) + 1 = 2n - 1$, which exceeds $2n-2$. A counting argument, and no case analysis at all.
The habit worth building is to reach for the degree total whenever a question mentions degrees, leaves or edges together. It is nearly always shorter than the picture.
Using $n-1$ edges as a definition. It characterises a tree only together with connectivity or acyclicity. A triangle plus an isolated vertex has four vertices and three edges and is not a tree.
Assuming a shape. Trees in computer science often have a root and a direction; the graph-theoretic tree has neither, and no vertex is special.
Expecting the leaf count to be determined. A path on $n$ vertices has two leaves and a star has $n-1$; both are trees.
Forgetting the lemma in the induction. 'Remove a leaf' is only a step once you have said why a leaf exists.
The definition is connected and acyclic, and nothing about the picture is part of it. A single vertex is a tree; a path is a tree; a star is a tree. Conversely a drawing with branches that meet again is not a tree however tree-like it looks, because the meeting closes a cycle. When a question asks whether something is a tree, count the edges and check connectivity: the picture is there to help you find the answer and is never the reason for it.
A graph has $9$ vertices and $8$ edges. The count is right for a tree, so the question is not yet settled.
The edge count is necessary and not sufficient.
Check connectivity: start anywhere and walk. If every vertex is reached, the graph is connected with $n-1$ edges, which is one of the four equivalent descriptions.
One further check is enough.
If some vertex is unreachable, the graph is a forest with at least two pieces, and with $8$ edges on $9$ vertices in two pieces it must contain a cycle.
The failure tells you what is there instead.
Suppose a tree on $n \ge 2$ vertices had at most one leaf. Every other vertex has degree at least two.
Assume the opposite and count.
Then the degrees add to at least $2(n-1) + 1 = 2n - 1$.
The smallest possible total, given the assumption.
But a tree's degrees add to $2(n-1) = 2n - 2$, which is smaller. Contradiction, so there are at least two leaves — proved by counting, with no picture and no cases.
The handshake lemma does the whole of the work.
The degrees add to $2(10 - 1) = 18$. Let there be $L$ leaves, so $10 - L$ vertices of degree three.
Total degree first, then name the unknown.
Then $L + 3(10 - L) = 18$, so $30 - 2L = 18$ and $L = 6$.
One linear equation.
Six leaves and four vertices of degree three. No picture was drawn and none was needed — which is the point of having a formula for the degree total, and is why the handshake lemma is the first thing to reach for whenever degrees are mentioned.
A tree is a path of five vertices, so it has $5$ vertices. Fill in its edges and its leaves.
| How many | |
|---|---|
| Edges | |
| Leaves |
A tree has $13$ vertices. How many edges?
Answer:
A connected graph on $6$ vertices is given. Put in order the steps of building a spanning tree inside it.
Number the steps in order (write the number in the box):
A tree has $7$ vertices, $4$ of them leaves. What do the degrees of the other vertices add up to?
Answer:
Build the induction proving that every tree with $n$ vertices has $n - 1$ edges.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A tree is a star with three spokes, so it has $4$ vertices. Fill in its edges and its leaves.
| How many | |
|---|---|
| Edges | |
| Leaves |
You can recognise a tree, count its edges and degrees, and build a spanning tree. Say in your own words why the edge count alone does not make a graph a tree, and why the induction has to remove a leaf rather than add one. Next: the walks that use every edge exactly once, and the degree condition that decides whether one exists.
10. Your turn: a tree has $10$ vertices and every vertex has degree $1$ or $3$. How many leaves?, step 3