Lecture 14: Tree
Definition 1 Let G be a graph. A vertex v of G is called a cut-vertex if G − v has more components
than G.
Theorem 1 Let G be a connected graph with |G| ≥ 2 and let v ∈ V (G).
a: If deg(v) = 1, then G − v is connected, so that v is never a cut-vertex.
b: If G − v is connected, then either deg(v) = 1 or v is on a cycle.
Proof: (a) Let a, b ∈ V (G − v), a ̸= b. Since G is connected there is a a − b path in G. Eveidently
the vertex v can not be the internal vertex of this path, as the degree of internal vertex is ≥ 2. So the
path a − b is available in G − v. So, G − v is connected.
(b) Assume G − v is connected. If deg(v) = 1, then nothing to prove. So let deg(v) ≥ 2. To show that
v is on a cycle in G. Let u and w be two distinct neighbors of v. Since G − v is connected, there is a
path (u = u1 , u2 , . . . , uk = w) in G − v. Then (u = u1 , u2 , . . . , uk = w, v) is a cycle.
Definition 2 Let G be a graph. An edge e in G is called a cut-edge or a bridge if G − e has more
connected components than that of G.
Proposition 1 Let G be connected and let e = uv be a cut-edge. Then G − e has two components, one
containing u and the other containing v.
Proof: If G − e is not disconnected, then by definition, e can not be a cut edge. So G − e has at least
two components. Let Gu (respectively, Gv ) be the component containing the vertex u (respectively,
v). We claim that these are the only components.
Let w ∈ V (G). Since G is connected, there is a path, say P , from w to u. Moreover, either P contains
v as its internal vertex or P does not contain v. In the first case, w ∈ V (Gv ) and in the latter case,
w ∈ V (Gu ). Thus, every vertex of G is either in V (Gv ) or in V (Gu ) and hence the required result
follows.
Theorem 2 Let G be a graph and let e be an edge. Then, e is a cut-edge iff e is not on a cycle.
Proof: Suppose e = uv is a cut-edge of G. Let F be the component of G that contains e. Then, by
the above Proposition, F − e has two components, namely, Fu that contains u and Fv that contains v.
Let if possible, C = (u, v = v1 , . . . , vk = u) be a cycle containing e = uv. Then (v = v1 , . . . , vk = u) is
a u − v path in F − e. Hence, F − e is still connected, a contradiction. Thus, e cannot be on any cycle.
1
Conversely, let e = uv be an edge which is not on any cycle. Now, suppose that F is the component
of G that contains e. We need to show that F − e is disconnected. Let if possible, there is a u − v
path, say (u = u1 , . . . , uk = v), in F − e. Then, (v, u = u1 , . . . , uk = v) is a cycle containing e. A
contradiction to e not lying on any cycle.
Definition 3 A connected graph G with no cycles is called a tree. A collection of trees is called a
forest.
Proposition 2 A tree on n vertices has n − 1 edges.
Proof: We apply induction on n. Take a tree on n ≥ 2 vertices and delete an edge e. Then, we get
two subtrees T1 , T2 of order n1 , n2 , respectively, where n1 + n2 = n. So, E(T ) = E(T1 ) ∪ E(T2 ) ∪ {e}.
By induction hypothesis |E(T )| = |E(T1 )| + |E(T2 )| + 1 = n1 − 1 + n2 − 1 + 1 = n1 + n2 − 1 = n − 1.
Corollary 1 A tree with at least two vertices has at least two pendant vertices.
P
Proof: Let T be a tree on n ≥ 2 vertices. Then v∈V (T ) deg(v) = 2|E(T )| = 2n − 2. Suppose T has
k pendent vertices. Then the remaining vertices, accept these k vertices, have degree ≥ 2. Then by
P
Handshaking Lemma, v∈V (T ) deg(v) ≥ 2k + 2(n − k) = 2n − k. Then by the above expression of
degree sum, k ≥ 2.
We now prove that the following statements that characterize trees are equivalent.
Theorem 3 Let G = (V, E) be a graph with |V | = n and |E| = m. Then f.s.a.e.
1. G is a tree.
2. Let u, v ∈ V . Then there is a unique path from u to v.
3. G is connected and n = m + 1.
Proof: (1 ⇒ 2): Since G is connected, for each u, v ∈ V , there is a path from u to v. On the contrary,
let us assume that there are two distinct u − v paths P1 and P2 . Then by earlier result, the subgraph
P1 ∪ P2 contains a cycle. This contradicts the assumption that G is a tree (it has no cycle).
(2 ⇒ 3): We prove this by induction on the number of vertices of a graph. The result is clearly true
for n = 1 or n = 2. Let the result be true for all graphs that have n or less than n vertices. Now,
consider a graph G on n + 1 vertices that satisfies the condition 2. The uniqueness of the path implies
that if we remove an edge, say e ∈ E, then the graph G will become disconnected. That is, G \ e will
have exactly two components. Let the number of vertices in the two components be n1 and n2 . Then
n1 , n2 ≤ n and n1 + n2 = n + 1. Hence, by induction hypothesis, the number of edges in G − e equals
2
(n1 − 1) + (n2 − 1) = n1 + n2 − 2 = n − 1 and hence the number of edges in G equals n − 1 + 1 = n.
Thus, by the principle of mathematical induction, the result holds for all graphs that have a unique
path from each pair of vertices.
(3 ⇒ 1): It is already given that G is a connected graph. We need to show that G has no cycle. So, on
the contrary, let us assume that G has a cycle of length k. Then this cycle has k vertices and k edges.
Now, consider the n − k vertices that do not lie of the cycle. Then for each vertex (corresponding to
the n − k vertices), there will be a distinct edge incident with it on the smallest path from the vertex to
the cycle. Hence, the number of edges will be greater than or equal to k + (n − k) = n. A contradiction
to the assumption that the number of edges equals n − 1. Thus, the required result follows.