Lesson 8

Each of the graphs shown above is a tree. A tree is a connected acyclic graph. It is not difficult to check that every graph above is indeed connected and does not contain cycles. Also, some of the graphs above are just paths:

There are many ways of defining a tree. Below, we show three of them and prove that they are equivalent. Throughout the whole section we assume that the considered graphs are undirected.

Theorem. The following definitions are equivalent.

1. A tree is a connected graph without cycles.
2. A tree is a connected graph on \(n\) vertices with \(n-1\) edges.
3. A tree is a graph having a unique simple path between any pair of its vertices.

Proof. We prove the theorem by establishing the following implications: \[1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 1.\]

• \(1 \Rightarrow 2.\)  Need to prove that a connected acyclic graph on \(n\) vertices has \(n-1\) edges. We prove this by induction on \(n\). The base case \(n=1\) is clear. For the induction step \(n-1 \to n\), take a connected acyclic graph on \(n\) vertices and remove one of its edges. This breaks the graph into two connected components with \(n_{1}\) and \(n_{2}\) vertices such that \(n_{1}+n_{2}=n\) (if the resulting graph contained a single connected component, the original graph would not be acyclic). Clearly, both components are connected and acyclic. By the induction hypothesis, they have \(n_{1}-1\) and \(n_{2}-1\) edges, respectively. Hence, the number of edges of the original graph is \[(n_{1}-1)+(n_{2}-1)+1=n_{1}+n_{2}-1=n-1.\]


• \(2 \Rightarrow 3.\)  Need to show that in any connected graph on \(n\) vertices with \(n-1\) edges there is a unique path between any pair of vertices. Assume that there are two paths between some pair of vertices. If these two paths do not share edges, then their union contains a simple cycle. For example, the union of two paths \[A-E-C \quad\text{and}\quad A-B-F-C\] is a cycle \[A-E-C-F-B-A.\]

  

  The paths however may share some edges: \[A - E - D - G - H - C \quad\text{and}\quad A - E - F - B - G - H - C.\] In this case, these two paths still contain a simple cycle: \[E - D - G - B - F - E.\]

  

  Fix such a cycle. It contains \(m\) vertices and \(m\) edges. Let's recover all edges of the graph one by one starting from this cycle. In order to connect all vertices, we have to add at least \(n-m\) edges. But then, the number of edges is at least \(n\), a contradiction.


• \(3 \Rightarrow 1.\)  Need to show that a graph having a unique simple path between any two vertices is connected and acyclic. Since for any pair of vertices, there is a path joining them, the graph is connected. If it had a cycle, there would be at least two paths between any two vertices of this cycle. For example, in a cycle \[A-B-C-D-E-A\] there are two paths between \(A\) and \(C\): \[A-B-C \quad\text{and}\quad A-E-D-C.\]
  

  

◼