LECTURE 3.3.
TREES
Course outcome to be covered:
CO4: Apply and recognized about the Trees
1.1 THEOREMS ON TREES
In this lecture we will study the fundamental theorems on trees
which are very useful in understanding the various concepts of trees.
1.2 TOPIC OBJECTIVES:
This topic will be helpful in understanding various properties of
trees.
The theorems discussed in this lecture will help the students to
make the concept more clear and solve many problems.
1.3 STRUCTURE:
Introduction
Fundamental theorems on trees
1.4 INTRODUCTION
We have already studied in our previous lectures about the trees, their
different types, many properties with examples. Now in this lecture we
will study the fundamental theorems used in trees and we will prove
them too.
1.5 THEOREM 1
STATEMENT
Prove that finite connected graph is Eulerian iff each vertex is of even
degree.
PROOF
Necessity Let G (V, E) be an Euler graph.
Thus G contains an Euler line Z, which is a closed walk. Let this walk
start and end at the vertex u ∈ V.
Since each visit of Z to an intermediate vertex v of Z contributes two to
the degree of v and since Z traverses each edge exactly once, d (v) is
even for every such vertex.
Each intermediate visit to u contributes two to the degree of u, and also
the initial and final edges of Z contribute one each to the degree of u.
So the degree d (u) of u is also even.
Sufficiency
Let G be a connected graph and let degree of each vertex of G be even.
Assume G is not Eulerian and let G contain least number of edges.
Since δ ≥ 2, G has a cycle. Let Z be a closed walk in G of maximum
length.
Clearly, G−E (Z) is an even degree graph.
Let C1 be one of the components of G−E(Z).
As C1 has less number of edges than G, it is Eulerian and has a vertex v
in common with Z. Let Z 0 is an Euler line in C1.
Then Z 0 ∪Z is closed in G, starting and ending at v. Since it is longer
than Z, the choice of Z is contradicted.
Hence G is Eulerian.
1.6 THEOREM 2
STATEMENT
Any connected graph with n vertices and n-1 edges is a tree.
PROOF
Let G be a connected graph with n vertices and n − 1 edges. We show
that G contains no cycles.
Assume to the contrary that G contains cycles.
Remove an edge from a cycle so that the resulting graph is again
connected.
Continue this process of removing one edge from one cycle at a time till
the resulting graph H is a tree.
As H has n vertices, so number of edges in H is n−1.
Now, the number of edges in G is greater than the number of edges in H.
So n−1 > n−1, which is not possible.
Hence, G has no cycles and therefore is a tree.
1.7 THEOREM 3
STATEMENT
A connected graph G is called a tree if removal of any of its edges
makes G disconnected.
PROOF
Let the graph G be minimally connected (means if removal of any of its
edges makes G disconnected).
Then G has no cycles and therefore is a tree.
Conversely, let G be a tree.
Then G contains no cycles and deletion of any edge from G disconnects
the graph.
Hence G is minimally connected.
1.8 THEOREM 4
STATEMENT
Show that the following properties of trees are equivalent:
A) G is tree
B) There exists a unique path between every two vertices of G.
C) G does not hold any closed path and it is connected.
PROOF
(i)A ==> B i.e. if G is a tree then there exist a unique path between every
two vertices of G.
Let G be a graph and let there be exactly one path between every pair of
vertices in G. So G is connected.
Now G has no cycles, because if G contains a cycle, say between
vertices u and v, then there are two distinct paths between u and v,
which is a contradiction.
Thus G is connected and is without cycles.
Therefore it is a tree.
Conversely, let G be a tree.
Since G is connected, there is at least one path between every pair of
vertices in G.
Let there be two distinct paths between two vertices u and v of G. The
union of these two paths contains a cycle which contradicts the fact that
G is a tree.
Hence, there is exactly one path between every pair of vertices of a tree.
(ii)A ==> C i.e. if G is a tree with n vertices, (n-1) edges and no circuit
then it is a connected.
Let the graph G is disconnected then there exist at least two components
G1 and G2 say.
Each of the components is circuit-less as G is circuit-less.
Now to make a graph G connected we need to add one edge e between
the vertices Vi and Vj, where Vi is the vertex of G1 and Vj is the vertex
of component G2.
Now the number of edges in G = (n – 1) +1 =n.
Now, G is connected graph and circuit-less with n vertices and n edges,
which is impossible because the connected circuit-less graph is a tree
and tree with n vertices has (n-1) edges.
So the graph G with n vertices, (n-1) edges and without circuit is
connected.
Hence the given statement is proved.
(iii) B==>C
As A ==> B and A ==> C
Therefore, the statements B and C are also equivalent.
I.e. B==>C
Summary
In today’s lecture the fundamental theorems on trees have been
discussed and proved. They are summarized as below:
The finite connected graph is Eulerian iff each vertex is of even
degree.
Any connected graph with n vertices and n-1 edges is a tree.
A connected graph G is called a tree if removal of any of its edges
makes G disconnected.
If G is a tree then there exists a unique path between every two
vertices of G.
If G is a tree with n vertices, (n-1) edges and no circuit then it is a
connected.
Frequently asked questions
Q1 Can a tree has a circuit?
ANS A connected graph without any circuit is called a Tree. In other
words, a tree is an undirected graph G that satisfies any of the following
equivalent conditions: Any two vertices in G can be connected by a
unique simple path.
Q2 Can a tree is disconnected?
ANS so a tree has the smallest possible number of edges for a connected
graph. Any fewer edges and it will be disconnected. But of course,
graphs with n-1 vertices can be disconnected.
REFERENCES
WEB LINKS
1 http://www.btechsmartclass.com/data_structures/tree-
terminology.html
2 http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%204.PDF
VIDEO LINKS
1 https://youtu.be/zEQZpTizgLo
2 https://youtu.be/dfrnH4BfTRo
APPLICATIONS
In mathematics, a theorem is a non-self-evident statement that has been
proven to be true, either on the basis of generally accepted statements
such as axioms or on the basis of previously established statements such
as other theorems.
Practice questions
Q1 Show that a tree with n vertices has n−1 edges.
Q2 Show that if G is cycle free and has (n-1) edges then it is connected.
