Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

12.4: Trees

( \newcommand{\kernel}{\mathrm{null}\,}\)

A special class of graphs that arise often in graph theory, is the class of trees. If a mathematician suspects that something is true for all graphs, one of the first families of graphs for which s/he will probably try to prove it, is the family of trees because their strong structure makes them much easier to work with than many other families of graphs.

Definition: Tree, Forest, and Leaf

  • A tree is a connected graph that has no cycles.
  • A forest is a disjoint union of trees. So a forest is a graph that has no cycles (but need not be connected).
  • A leaf is a vertex of valency 1 (in any graph, not just in a tree or forest).

Notice that the graph Pn is a tree, for every n1. We prove some important results about the structure of trees.

Proposition 12.4.1

Let T be a connected graph with no cycles. Then deleting any edge from T disconnects the graph.

Proof

If T has no edges, the statement is vacuously true. We may thus assume that T has at least one edge. Let {u,v} be an arbitrary edge of T. (Since a loop is a cycle, we must have uv even if we were not assuming that our graphs are simple.)

Towards a contradiction, suppose that deleting {u,v} from T does not disconnect T. Then by the definition of a connected graph, there is a uv walk in T{u,v}. By Proposition 12.3.1, the shortest uv walk in T{u,v} must be a uv path. If we take this same walk in T and add u to the end, this will still be a walk in T since T contains the edge uv. Since the walk in T{u,v} was a path, no vertices were repeated. Adding u to the end of this walk makes a walk (certainly of length at least 2) in which no vertex is repeated except that the first and last vertices are the same: by definition, a cycle. Thus, T has a cycle, contradicting our hypothesis. This contradiction serves to prove that deleting any edge from T disconnects the graph.

Since a tree is a connected graph with no cycles, this shows that deleting any edge from a tree will disconnect the graph.

Proposition 12.4.2

Every tree that has at least one edge, has at least two leaves.

Proof

We prove this by strong induction on the number of vertices. Notice that a (simple) graph on one vertex must be K1, which has no edges, so the proposition does not apply. Therefore our base case will be when there are 2 vertices.

Base case: n=2. Of the two (unlabeled) graphs on 2 vertices, only one is connected: K2 (or P1; these are isomorphic). Both of the vertices have valency 1, so there are two leaves. This completes the proof of the base case.

Induction step: We begin with the strong inductive hypothesis. Let k2 be arbitrary. Suppose that for every 2ik, every tree with i vertices has at least two leaves. (Since i2 and a tree is a connected graph, every tree on i vertices has at least one edge, so we may omit this part of the hypothesis.)

Let T be a tree with k+1 vertices. Since k+1>1, T has at least one edge. Choose any edge {u,v} of T, and delete it. By Proposition 12.4.1, the resulting graph is disconnected. By Proposition 12.3.2, it cannot have more than two connected components, so it must have exactly two connected components. Furthermore, by the proof of that proposition, the components are Tu (the connected component that contains the vertex u) and Tv (the connected component that contains the vertex v).

Since T has no cycles, neither do Tu or Tv. Since they are connected components, they are certainly connected. Therefore, both Tu and Tv are trees. Since u is not a vertex of Tv and v is not a vertex of Tu, each of these trees has at most k vertices.

If both Tu and Tv have at least two vertices, then we can apply our induction hypothesis to both. This tells us that Tu and Tv each have at least two leaves. In particular, Tu must have some leaf x that is not u, and Tv must have some leaf y that is not v. Deleting uv from T did not change the valency of either x or y, so x and y must also have valency 1 in T. Therefore T has at least two leaves. This completes the induction step and therefore the proof, in the case where Tu and Tv each have at least two vertices. We must still consider the possibility that at least one of Tu and Tv has only one vertex.

Since k+13, at least one of Tu and Tv must have two vertices, so only one of them can have only one vertex. Without loss of generality (since nothing in our argument so far made any distinction between u and v, we can switch u and v if we need to), we may assume that Tv has only one vertex, and Tu has at least two vertices. Applying our induction hypothesis to Tu, we conclude that Tu has some leaf x that is not u, and that is also a leaf of T. Furthermore, since Tv has only one vertex, this means that deleting the edge uv left v as an isolated vertex, so uv was the only edge incident with v in T. Therefore, v is a leaf of T. Thus, T has at least two leaves: x and v. This completes the induction step and therefore the proof, in the case where at least one of Tu and Tv has only one vertex. Since we have dealt with all possibilities, this completes our induction step.

By the Principle of Mathematical Induction, every tree that has at least one edge, has at least two leaves.

The next result will be left to you to prove.

Proposition 12.4.3

If a leaf is deleted from a tree, the resulting graph is a tree.

Theorem 12.4.1

The following are equivalent for a graph T with n vertices:

  1. T is a tree;
  2. T is connected and has n1 edges;
  3. T has no cycles, and has n1 edges;
  4. T is connected, but deleting any edge leaves a disconnected graph.
Proof

We will prove that the statements are equivalent by showing that 12341. Thus, by using a sequence of implications, we see that any one of the statements implies any other.

(12) We assume that T is a tree, and we would like to deduce that T is connected and has n1 edges. By the definition of a tree, T is connected. We will use induction on n to show that T has n1 edges.

Base case: n=1. There is only one (unlabeled) graph on one vertex, it is K1, so TK1, which has no edges. Since 0=n1, this completes the proof of the base case.

Inductive step: We begin with the inductive hypothesis. Let k1 be arbitrary, and suppose that every tree on k vertices has k1 edges.

Let T be an arbitrary tree with k+1 vertices. Since k+12 and T is connected, T must have at least one edge, so by Proposition 12.4.2, T has at least two leaves. Let v be a leaf of T. By Proposition 12.4.3, T{v} is a tree. Also, T{v} has k vertices, so we can apply our induction hypothesis to conclude that T{v} has k1 edges. Since v was a leaf, T has precisely one more edge than T{v}, so T must have k=(k+1)1 edges. This completes our inductive step.

By the Principle of Mathematical Induction, every tree on n vertices has n1 edges.

(23) We assume that T is connected and has n1 edges. We need to deduce that T has no cycles.

Towards a contradiction, suppose that T has a cycle. Repeatedly delete edges that are in cycles until no cycles remain. By Proposition 12.3.3 (used repeatedly), the resulting graph is connected, so by definition it is a tree. Since we have already proven that 12, this tree must have n1 edges. Since we started with n1 edges and deleted at least one (based on our assumption that T has at least one cycle), this is a contradiction. This contradiction serves to prove that T must not have any cycles.

(34) We assume that T has no cycles, and has n1 edges. We must show that T is connected, and that deleting any edge leaves a disconnected graph. We begin by showing that T is connected; we prove this by induction on n.

Base case: n=1. Then TK1 is connected.

Inductive step: We begin with the inductive hypothesis. Let k1 be arbitrary, and suppose that every graph on k vertices that has k1 edges and no cycles, is connected.

Let T be an arbitrary graph with k+1 vertices that has k edges and no cycles. By Euler’s handshaking lemma,

vVd(v)=2k.

If each of the k+1 vertices had valency 2 or more, then we would have

vVd(v)2(k+1)

(this is a lot like the Pigeonhole Principle in concept, but the Pigeonhole Principle itself doesn’t apply to this situation). Since 2k<2(k+1), there must be some vertex v that does not have valency 2 or more. Delete v. In so doing, we delete at most 1 edge, since v has at most 1 incident edge. Thus, the resulting graph has k vertices and k or k1 edges, and since T has no cycles, neither does T{v}.

If T{v} has k edges, then deleting any of the edges results in a graph on k vertices with no cycles and k1 edges, which by our inductive hypothesis must be connected. Therefore T{v} is a connected graph that remains connected after any edge is deleted. By Proposition 12.4.1 (in the contrapositive), this means that T{v} must contain a cycle, but this is a contradiction. This contradiction serves to prove that T{v} cannot have k edges.

Thus, T{v} has k1 edges and k vertices, and no cycles. By our inductive hypothesis, T{v} must be connected. Furthermore, the fact that T{v} has k1 edges means that v is incident to an edge, which must have its other endvertex in T{v}. Therefore T is connected. This completes the inductive step.

By the Principle of Mathematical Induction, every graph on n vertices with no cycles and n1 edges is connected.

It remains to be shown that deleting any edge leaves a disconnected graph, but now that we know that T is connected, this follows from Proposition 12.4.1.

(41) We assume that T is connected, but deleting any edge leaves a disconnected graph. By the definition of a tree, we must show that T has no cycles. This follows immediately from Proposition 12.3.3.

Exercise 12.4.1

  1. Prove Proposition 12.4.3.
  2. Draw a tree on 6 vertices.
  3. There are two non-isomorphic trees on 4 vertices. Find them.
  4. There are 11 non-isomorphic graphs on 4 vertices. Draw all 11, and under each one indicate: is it connected? Is it a forest? Is it a tree?

[Hint: One has 0 edges, one has 1 edge, two have 2 edges, three have 3 edges, two have 4 edges, one has 5 edges, and one has 6 edges.


This page titled 12.4: Trees is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.

  • Was this article helpful?

Support Center

How can we help?