Module - 5

Introduction to Graph Theory: Definitions and

Examples, Sub graphs, Complements, and Graph
Isomorphism, Walk, Euler Circuit and Trail,
Konigsberg Bridge Problem.

Trees: Definitions, Properties, and Examples,

Routed Trees, Trees and Sorting, Weighted Trees
and Prefix Codes.
Dr G Manjula Associate Professor,DSATM 1
 Introduction -Trees
A tree is a connected simple undirected graph with no cycles.

T1 T2 T3

• T1 and T2 are the trees and T3 is forest

• A forest is a disconnected trees with no cycles.

• Each of these trees possesses at least two pendant vertices. A

pendant vertex of a tree is also called a leaf. 2
Dr G Manjula Associate Professor,DSATM
 Theorem 1
In a tree, there is one and only one path between every pair of vertices

› Proof: Let T be tree. Then T is connected simple graph.

› Since T is connected, there must be at least one path between every

pair of vertices.

› If there are two paths between a pair of vertices of T, the union two
paths become a cycle, and T cannot be tree.

› Thus, between every pair of vertices in a tree there must exist one
and only one path.

› ∴ In a tree, there is one and only one path between every pair
of vertices Dr G Manjula Associate Professor,DSATM 3
 Theorem 2
If in a graph G there is one and only one path between every pair
of vertices, then G is a tree.

Proof:
› There is the existence of a path between every pair of vertices so
we assume that graph G is connected.
› A cycle in a graph implies that there is at least one pair of vertices a
and b, such that there are two distinct paths between a and b.
› Since G has one and only one path between every pair of vertices.
› G cannot have any cycle. Hence graph G is a tree.

› ∴ In a graph G there is one and only one path between every

pair of vertices, then G is a tree.

Dr G Manjula Associate Professor,DSATM 4

 Theorem 3
A tree with n vertices has n−1 edges
Proof:
› Let n be the number of vertices in a tree (T).
› If n=1, then the number of edges=0.
› If n=2 then the number of edges=1.
› If n=3 then the number of edges=2.

Hence, the statement (or result) is true for n=1, 2, 3.

› Let the statement be true for n=m. Now we want to prove that it is
true for n=m+1.

› Let e be the edge connecting vertices say Vi and Vj. Since G is a

tree, then there exists only one path between vertices Vi and Vj.
Dr G Manjula Associate Professor,DSATM 5
Theorem 3
cont..

6
Dr G Manjula Associate Professor,DSATM
 Theorem 4
A connected graph is a tree if and only if it is minimally connected.

Proof:
› Let the graph G is minimally connected, i.e; removal of one edge make it
disconnected.
› Therefore, there is no circuit. Hence graph G is a tree.

› Conversely, let the graph G is a tree i.e; there exists one and only one path
between every pair of vertices and we know that removal of one edge from
the path makes the graph disconnected.

› Hence graph G is minimally connected.

› ∴ A connected graph is a tree if and only if it is minimally connected.

Minimally Connected Graph: A connected graph is minimally connected

7
if removal of any one edge Drfrom it d is connects graph
G Manjula Associate Professor,DSATM
 Problems
(a) Show that the complete graph Kn is not a tree when n >
2.
(b) Show that the complete bipartite graph K r,s is not
a tree when r, s>= 2

(a)If v1, v2, v3 are any three vertices of Kn where n > 2, then the
closed walk v1, v2, v3, v1 is a cycle in Kn. Since Kn has a cycle, it
cannot be tree.

(b)Let v1 and v2 be any two vertices in the first bipartite and v1’
and v2’ in other bipartite of Kr,s with s ≥ r ≥ 2. then, the closed
walk v1 v1’ v2 v2’ v1 is a cycle in Kr,s . Since Kr, s has a cycle, it
cannot be tree.
Dr G Manjula Associate Professor,DSATM 8
 Problems
Prove that a tree with two or more vertices contains at least two
leaves (pendant vertices)
› Proof: Let T be tree with n vertices where n ≥ 2. then it has n -1 edges.
› The sum of the degrees of n vertices must be equal to 2(n – 1).
› Thus, if d1, d2 d3, …..,dn are the degrees of vertices of T, we have
d1+ d2 + d3 ....,dn = 2(n -1) = 2n - 2
› If each of d1, d2 d3, …..,dn is ≥ 2, then their sum must be at least 2n. Since, this is
not true, at least one of the d’s is less than 2.
› Thus, there is d which is equal to 1, let us take d1 = 1
› 1+ d2 + d3 ....,dn -1 = 2 (n -1) = 2n -2
› d2 + d3 ....,dn -1 = 2n -2 – 1
› d2 + d3 ....,dn -1 = 2n – 3
› This is possible only if at least one of d2 d3, …..,dn is equal to 1.
› Thus in T, there are at least two vertices with degree 1.
› That is there are at least two pendant vertices (leaves)

vertices) Dr G Manjula Associate Professor,DSATM 9

› ∴ A tree with two or more vertices contains at least two leaves
 Problems
Show that if a tree has exactly two pendant vertices, the degree of
every non-pendant vertex is two.

Dr G Manjula Associate Professor,DSATM 10

 Problems
Show that in a tree if the degree of every non pendant vertex is 3,
then number of vertices in the tree is an even number
› Let n be the number of vertices in a tree T.

› Of these, let k be the number of pendant vertices

› Then, Each of non-pedant vertex is of degree 3, the

sum of the degrees of vertices is k + 3(n-k)

› This must be equal to 2(n-1)

› i.e. k + 3 (n - k) = 2 (n -1)
› n = 2k -2 = 2 (k -1)
› This shows that n is even number

› ∴ In a tree if the degree of every non pendant vertex is 3, then number

Dr G Manjula Associate Professor,DSATM 11
of vertices in the tree is an even number
 Problems
If a tree T has four vertices of degree 2, one vertex of degree 3,
two vertices of degree 4 and one vertex of degree 5, find the
number of leaves in T
› Let N be the number of leaves (pendant vertices) in T,

› Total number of vertices = N + 4 + 1 + 2 + 1 = N + 8

› Sum of the degrees of vertices = (N x 1) + (4 x 2) + (1 x 3) + (2 x 4)
+ (1 x 5) = N + 24
› Since T has N + 8 vertices it has N + 8 -1 edges = N + 7 edges
› N + 24 = 2 ( N + 7)
› N =10
› Thus, the given tree has 10 leaves.

Dr G Manjula Associate Professor,DSATM 12

 Problems for Practice
1. If a tree has 2020 vertices, find the sum of the degrees of the
vertices.

2. Suppose that a tree T has two vertices of degree 2, four vertices

degree 3 and three vertices of degree 4. find the number of
pendant vertices in T.

3. Let T1 = (V1, E1) and T2 = (V2, E2) be two trees. If |E1|=19 and
|V2| = 3|V1|, determine |V1|, |V2| and |E2|.

4. Suppose that a T has N1 vertices of degree 1, N2 vertices of

degree 2, N3 vertices of degree 3, . . . , Nk vertices of degree k.
Prove that. Dr G Manjula Associate Professor,DSATM
13
 Rooted Tree
• A directed tree T is said to be a Rooted Tree
(i) T contains a unique vertex called the root, whose in-degree
is equal to zero.
(ii)
The in-degrees of all other vertices of T are equal to one.

Not a rooted tree Rooted tree

Dr G Manjula Associate Professor,DSATM 14
 Rooted Tree
• a is the parent of b, b is the child of a,

• c, d, e are siblings (Common parent)

• a, b, d are ancestors of f

• c, d, e, f, g are descendants of b

• c, e, f, g are leaves of the tree (deg=1)

• b, d are internal vertices of the tree (at least one

child)

• subtree with d as its root:

Dr G Manjula Associate Professor,DSATM 15
 m-ary Tree
A rooted tree T is called an m-ary tree if every internal vertex of T is of
out-degree ≤ m; that is if every internal vertex of T has at most m
children.

A rooted tree T is called complete m-ary tree If every internal vertex

of T is of out-degree m;

That is if every internal vertex of T has exactly m children.

Complete 3-ary tree 3-ary tree

Dr G Manjula Associate Professor,DSATM 16
 Binary Rooted Tree
Definition: If the outdegree of every vertex of T at most equal to two.
Or
› Equivalently, every vertex of T has at the most two children.

› A complete m-ary tree for which m =2 is called complete binary

tree.

› In other words, a rooted tree T is called complete binary tree if every

internal vertex of T is of out degree 2; that is if every internal
vertex has exactly two children's.

Binary tree Dr G Manjula Associate Professor,DSATM 17

Complete Binary
 Full Binary Rooted Tree
Definition: Let T be a complete binary tree of height h. Then T
is called a full binary tree if all the leaves in T are at level h.
Note: The height of binary tree is the longest path from root node
to any leaf node in the tree.

Full Binary tree

Not a full Binary treeDr G Manjula Associate Professor,DSATM 18
 Balanced Rooted Tree
Definition: A rooted tree of height h is said to be balanced if the
level number of every leaf is h or h – 1.

Balanced Tree Not Balanced Tree

Dr G Manjula Associate Professor,DSATM 19

Let T be a complete m-ary tree of order n with p leaves and q
internal vertices.

Dr G Manjula Associate Professor,DSATM 20

(a) Find the number of internal vertices in a complete 5-ary tree
with 817 leaves.
(b) Find the number of leaves in a complete 6-ary tree of order
733.

Dr G Manjula Associate Professor,DSATM 21

A computer laboratory of a school has 10 computers that are to be
connected to a wall socket that has 2 outlets. Connections are
made by using extension cords that have 2 outlets each. Find the
least number of cords needed to get these computers set up for
use.

Dr G Manjula Associate Professor,DSATM 22

1. A class room contains 25 microcomputers that must be
connected to a wall socket that has 4 outlets. Connections are
made by using extension cords that have 4 outlets each. Find
the least number of cords needed to get this computer set up
for the class.

2. Find the number of vertices and the number of leaves in a

complete binary tree having 10 internal vertices.

Dr G Manjula Associate Professor,DSATM 23

 Sorting
Merge Sort is a divide and conquer algorithm. It works by
continually splitting a list into halves until both parts are sorted,
then the operation merge is performed to combine two lists into
one sorted new list.

Dr G Manjula Associate Professor,DSATM 24

 Merge Sort
Apply merge sort to the list {-1, 7, 4, 11, 5, -8, 15, -3, -2, 6, 10, 3}

{-1, 7, 4, 11, 5, -8, 15, -3, -2, 6, 10, 3}

{-1, 7, 4, 11, 5, -8} { 15, -3, -2, 6, 10, 3}

{-1, 7, 4} {11, 5, -8} { 15, -3, -2} { 6, 10, 3}

{-1, 7} {4} {11, 5} {-8} { 15, -3} { -2} { 6, 10} {3}

{-1} {7} {11} {5} { 15} { -3} {6} { 10}

The sublist obtained above are now merged as follows

Dr G Manjula Associate Professor,DSATM 25

 Merge Sort
Apply merge sort to the list {-1, 7, 4, 11, 5, -8, 15, -3, -2, 6, 10, 3}

{-1} {7} {11} {5} { 15} { -3} { 6 } { 10}

{-1, 7} {4} {5, 11} {-8} { -3, 15} { -2} { 6, 10} {3}

{-1, 4, 7} {-8, 5, 11} { -3, -2, 15}

{ 3, 6, 10}

{ -3, -2, 3, 6, 10, 15}

{-8, -1, 4, 5, 7, 11}

{ -8, -3, -2, -1, 3, 4, 5, 6, 7, 10, 11, 15}

The sorted version of the given list is -8, -3, -2, -1, 3, 4, 5, 6, 7, 10, 11, 15

Dr G Manjula Associate Professor,DSATM 26

 Prefix Code and Weighted Tree
•

Dr G Manjula Associate Professor,DSATM 27

 Optimal Tree and Optimal Prefix Code
Optimal Tree: Given set of weights, suppose we consider the set of all
complete binary trees to whose leaves these weights are assigned. A tree in this
set which carries the minimum weight is called an optimal tree for the weights.
For a given set of weights, there can be more than one optimal tree.

Optimal Prefix Code: The edges of the optimal tree are symbolically labelled
0(left child) and 1(right child) appropriately. This will facilitate to identify all
the vertices and leaves of the tree by binary sequences. These sequences
generates a prefix code for the symbols representing the leaves and the prefix
code is referred to as an optimal prefix code.
Example:

Optimal Prefix code

e:0
a : 10
t : 110
n : 1110
s : 1111
Dr G Manjula Associate Professor,DSATM 28
 Problems on optimal prefix
1.
code
Construct an optimal prefix code for the symbols a, o, q, u, y, z
that occur with frequencies 20, 28, 4, 17, 12, 7 respectively.

2. Obtain the optimal prefix code for the message ROAD IS GOOD.
Indicate the code.

Dr G Manjula Associate Professor,DSATM 29

 Problems on optimal prefix code
1. Construct an optimal prefix code for the symbols a, o, q, u, y, z that
occur with frequencies 20, 28, 4, 17, 12, 7 respectively.

Step 1: Arrange the symbols (vertices) such that their frequencies(weights) are in
increasing order.

q z y u a o
(4) (7) (12) (17) (20) (28)
Step 2: Two smallest weights (q, z) are added and the resulting weight (4+7=11) be
associated with new vertex say v1. A tree having v1 as root and (q, z) as its children is
drawn along with the other vertices in the increasing order of weights.

v1 (11)
y u a o
(12) (17) (20) (28)

q(4) Dr G Manjula Associate Professor,DSATM

z(7) 30
 Problems on optimal prefix code
Step 3: w(v1) + w(y) = 11 + 12 = 23 be associated with new vertex v2.
the vertices in the non decreasing order now is u(17) –
a(20)
–v2(23)-o(28). The tree with v2 as root and v1, y as children is drawn
along with other vertices in the increasing order.

u a o
v2(23)
(17) (20) (28)

v1 (11) y(12)

q (4) z(7)

Dr G Manjula Associate Professor,DSATM 31

 Problems on optimal prefix code
Step 4: w(u) + w(a) = 17 + 20 = 37 be associated with new vertex v3.
The vertices in the increasing order of weights is v2(23) – o(28) –v3(37).
The tree with v3 as root and u, a as children is drawn along with other
vertices in the increasing order.

v3(37)
v2(23)

o (28)

v1 (11) y(12)
u (17) a(20)

q (4) z(7)

Dr G Manjula Associate Professor,DSATM 32

 Problems on optimal prefix code
Step 5: w(v2) + w(o) = 23 + 28 = 51 be associated with new vertex v4.
The vertices in the increasing order of weights is v3(37) – v4(51). The
tree with v4 as root as also written

v4 (51)
v3(37)

v2(23) o (28)

u (17) a(20)
v1 (11) y(12)

q Z
(4) (7)
Dr G Manjula Associate Professor,DSATM 33
 Problems on optimal prefix code
Step 6: w(v3) + w(v4) = 37 + 51 = 88 be associated with new vertex v5.
This step being final one, this new vertex becomes the root of the tree be
denoted as v5 which will have v3 and v4 as its children.

v5 (88)

v4 (51)
v3(37)

v2(23)
u (17) o (28)
a(20)

v1 (11) y(12)

q(4) z(7)
Dr G Manjula Associate Professor,DSATM 34
 Problems on optimal prefix code
Huffmann optimal tree as follows
v5 (88)

0 1
v4 (51)
v3(37)

0 1 0 1
v2(23)
u (17) a(20) o (28)
0 1

v1 (11) y(12)
1
0

q(4) z(7)

The optimal prefix code for the symbols are tabulated Dr G Manjula
Associate
a o q u y z Professor,DSATM
01 11 1000 00 101 1001 35
 Problems on optimal prefix code
Huffmann optimal tree as follows
v5 (88)

0 1
v4 (51)
v3(37)

0 1 0 1
v2(23)
u (17) a(20) o (28)
0 1

v1 (11) y(12)
1
0

q(4)

z(7)

Weight of optimal tree is computed. Vertices q(4), z(7) are at level 4;

y(12) at level 3; u(17), a(20), o(28) at level 2. 36
Dr G Manjula Associate Professor,DSATM
 Problems
1. Obtain the optimal prefix code for the message ROAD IS GOOD. Indicate
the code.
2. Construct an optimal prefix code for the letters of the
word
ENGINEERING. Hence deduce the code.
3. Obtain
RECEIVED. the optimal
Indicate prefix
the code . code for the message
4. LETTER
Obtain the optimal prefix code for the message PROPOSAL
ACCEPTED. Indicate the code.
5. Obtain the optimal prefix code for the message
MISSION SUCCESSSFUL and Indicate Code.
6. Construct an optimal prefix code for the symbols a, b, c, . . i, j that
occur with frequencies 78, 16, 30, 35, 125, 31, 20, 50, 80, 3.
7. Construct an optimal tree for the given set of weights {4, 5, 25, 5, 8,
16}. Hence find the height of the optimal tree.
8. Using the weights 2, 3, 5, 10, 10, show that height of the Huffman
tree for a given set of weights is not unique. 37
Dr G Manjula Associate Professor,DSATM