KARNATAKA STATE OPEN UNIVERSITY

Mukthagangothri, Mysuru – 570006

[Link]. MATHEMATICS (CBCS)

(FOURTH SEMESTER)

II

Course-MMDSE – 4.4
GRAPH THEORY
 [Link]. MATHEMATICS
FOURTH SEMESTER (CBCS)

MMDSE 4.4 - GRAPH THEORY

 TABLE OF CONTENTS
Page No

Block I BASICS OF GRAPH THEORY

Unit-1 Graphs and Digraphs 1-17

Unit-2 Walks and Connectedness 18-28

Unit-3 The Problem of Ramsey, Extremal graph, Intersection graph 29-37

Unit-4 Operations on Graphs 38-48

Block II BLOCKS AND TREES

Unit-5 Cut-Vertices, Bridge and Blocks 49-60

Unit-6 Trees and its Properties 61-74

Unit-7 Centers and Centroids 75-78

Unit-8 Independent cycles and cocycles 79-82

Block III CONNECTIVITY

Unit-9 Connectivity and Edge Connectivity 83-88

Unit-10 Whitney’s Theorem 89-92

Unit-11 Menger’s Theorem 93-108

Unit-12 Euler and Hamiltonian Graphs 109-121

Block IV PLANARITY AND COLORABILITY

Unit-13 Planar Graphs 122-137

Unit-14 Colorability 138-143

Unit-15 The Five Color Theorem 144-146

Unit-16 The chromatic Polynomial of Graphs 147-154

 COURSE INTRODUCTION

The last three decades have witnessed an upsurge of interest and activity in graph theory,
particularly among applied mathematicians and engineers. Clear evidence of this is to be found in
an unprecedented growth in the number of papers and books being published in the field. In 1957
there was exactly one book on the subject (namely, Konig's Theorie der Endlichen und
Unendlichen Graphen). Now, sixty years later, there are hundreds of textbooks on graph theory,
and almost an equal number of proceedings of various seminars and conferences are available.

There are several reasons for the acceleration of interest in graph theory. It has become fashionable
to mention that there are applications of graph theory to some areas of physics, chemistry,
communication science, computer technology, electrical and civil engineering, architecture,
operational research, genetics, psychology, sociology, economics, anthropology, and linguistics.
The theory is also intimately related to many branches of mathematics, including group theory,
matrix theory, numerical analysis, probability, topology, and combinatorics. The fact is that graph
theory serves as a mathematical model for any system involving a binary relation. Partly because
of their diagrammatic representation, graphs have an intuitive and aesthetic appeal. Although there
are many results in this field of an elementary nature, there is also an abundance of problems with
enough combinatorial subtlety to challenge the most sophisticated mathematician. Hence the
course on graph theory in post-graduation level enriches the knowledge of the students in different
areas of mathematics and its applications.

The First block is on Basics of Graph theory, in which all terminologies used in the theory of
graphs are explained in detail. In the second block some special graphs like Blocks and Trees,
and their applications are explained. In block three, connectivity and Euler graph, Hamiltonian
graphs are explained. In the fourth block, concepts of planarity and colorability have been
covered.
 BLOCK – I

BASICS OF GRAPH THEORY

Page 1
 UNIT 1

GRAPHS AND DIGRAPHS

Structure:

1.0. Objectives

1.1. Introduction

1.2. Graph and Graph Representation

1.3. Degree of a Vertex

1.4. Some Special Graphs

1.5. Subgraphs

1.6. Isomorphism of Graphs

1.7. Summary

1.8. Keywords

1.9. Exercises

1.10. References

Page 2
1.0. Objectives
The objective of this unit is to make the learners conversant on –
 Define of Graph and its application
 Basic terminologies used in graph theory
 Varieties of graphs and subgraphs
 Isomorphism of graphs and graph invariants

1.1. Introduction

Many real-world situations can conveniently be described by means of a diagram consisting of a set
of points together with lines joining certain pairs of these points. For example, the points could
represent people, with lines joining pairs of friends; or the points might be communication centers,
with lines representing communication links. Notice that in such diagrams one is mainly interested in
whether two given points are joined by a line; the manner in which they are joined is immaterial. A
Mathematical abstraction of situations of this type gives rise to the concept of a graph.

Most graph theorists use personalized terminology in their books, papers, and lectures. In order to
avoid hairsplitting, it has been found convenient to adopt the procedure that each man state in
advance the graph theoretic language he would use. Even the very word "graph" has not been
sacrosanct. Some authors actually define a "graph" as a graph, but others intend such alternatives as
multigraph, pseudo graph, directed graph, or network. We believe that uniformity in graphical
terminology will never be attained, and is not necessarily desirable. Alas, it is necessary to present a
formidable number of definitions in order to make available the basic concepts and terminology of
graph theory. In this unit we explicate all the basic terminologies used to develop the course. Thus in
all the sense this unit is a very important and it is a base for the entire course.

Page 3
1.2. Graph and Graph Representation

A graph G = (V, E) consists of a non-empty set of objects V {v1, v2 , , v p }, whose elements are

called vertices (or points or nodes or junctions) and another set E {e1, e2 , , eq }, whose elements

are called edges (or lines or arcs or branches), such that each edge ek  E is identified with an

unordered pair {vi , v j } of elements of V.

¤ V is called the vertex set of G and denoted by V(G) and E is called the edge set of G and
denoted by E (G).

Instead, an unordered set E of two element subsets of V, if we consider ordered pair of elements of V,
then the graph G (V, E) is called directed graph or simply a digraph. The edge (x, y)  E is called a
directed edge from the vertex x to the vertex y.

¤ By a graph we mean always an undirected graph.

¤ A graph G = (V, E) is said to be finite if both V and E are finite, otherwise it is an infinite graph.

¤ If e = {x, y} is an edge of graph G (i.e. e  E) then e can also be written as e = xy or simply xy.

¤ If xy is an edge of graph G, then xy = yx.

¤ If (x, y) is an edge of a digraph, then (y, x) need not be an edge of it.

¤ The definition of graph permits an edge e of the form e = {x, x}, such an edge e is called self-
loop (or simply a loop).

¤ If e = xy is an edge of a graph G, then the vertices x and y are called end vertices of the edge e.

¤ If e = (x, y) is an edge of a digraph, then x is called initial (or starting) vertex and y is called
terminal (or end) vertex of e.

Representation of a Graph:
In diagrammatic representation of the graph G, the vertices of G is denoted by points/small-circle and
each edge e = xy is represented by joining a Jordan arc (may be a line) between the points x and y. In
the case of digraphs an orientation (an arrow) from x to y represents the directed edge (x, y).

Page 4
Example 1.2.1: The graph G = ({a, b, c, d, f, g}, {ab, ac, bc, gg, cf, ga}) is shown in the following
figure a
b

g
d
c
f

Example 1.2.2: The graph G = ({1, 2, 3, 4, 5}, {{x, y}: |x – y| =1}) is shown in the following figure

1 2 3 4 5

Example 1.2.3: The digraph G = ({1, 2, 3, 4}, {(x, y): x < y}) is shown in the following figure

1 2

4 3

Remark 1.2.1: Our definition of graph will not allow an edge more than once. However, we can
draw more than one edge between the same pair of vertices. Such edges are called parallel edges or
multiple edges and the graph is called multigraph (multiple graph). A graph having no multiple
edges and loops is called a simple graph. A graph having loops but no multiple edges is called
pseudo graph. To avoid ambiguity we always write graph instead of simple graph and other graphs
are mentioned clearly whenever we use it.

Remark 1.2.2: The cardinality of the vertex set V(G) (i.e. the number of vertices of G) is called
order of the graph G, usually denoted by the letter p (or n), and the cardinality of the edge set E(G)
(i.e. the number of edges of G) is called size of the graph G, usually denoted by the letter q (or m).
The graph G of order p and the size q is called a (p, q) – graph. Further by a graph G(p, q), we mean
a graph named G consisting of p vertices and q edges.

Problem 1.2.1: Show that the size of a simple graph of order n cannot exceed nC2 .

Solution: Let G be a graph of order n. Let V be a vertex set of G. Then cardinality of V is n and
elements of E are distinct two elements subsets of V. The number of ways we can choose two
elements from a set V of n elements is nC2. Thus E may not have more that nC2 elements (edges).

Page 5
Note:
¤ Let e = xy be an edge of a graph G. Then we have ‘x’ and ‘y’ are end vertices of e. If ‘x’ is an
end vertex of an edge e, then we say that the vertex ‘x’ and edge e are incident with (on or to)
each other.

¤ The vertices ‘x’ and ‘y’ of a graph G are said to be adjacent if e = xy be an edge of a graph G.

¤ Two edges e1 and e2 having a common end vertex are called adjacent edges.

¤ In a simple graph two adjacent edges cannot have more than one common end vertex.

1.3. Degree of a Vertex

The development of theory of graphs mainly depends on study of number of vertices for which each
vertex is adjacent. This leads to degree concept of vertices. The degree of a vertex v of a graph G,
denoted by deg(v), is the number of edges incident on v, with self-loop counted twice, in G.
Consider the graph G shown in the following figure

v3

g b
v1 a
v2

f c
e

v5 v4

Vertices of G Edges incident with Self-Loop Degree of the

the vertex vertex

v1 a, f, g g 4

v2 a, b, c --- 3

v3 b --- 1

v4 c, d, e --- 3

v5 d, e, f --- 3

Page 6
Note:
¤ Degree of a vertex is always a non-negative integer.
¤ If the degree of a vertex v is zero, then v is called an isolated vertex of G.
¤ If the degree of a vertex v is one, then the vertex v is called an end vertex or pendant vertex or a
leaf. The edge incident with the pendant vertex of G is called a pendant edge.

¤ Let v1, v2,......... , vn be the vertices of a graph G with deg (vi) ≥ deg (vi+1), for all i, 1 ≤ i < n. Then
the sequence deg (v1), deg (v2),........., deg (vn) is called a degree sequence of a graph G.

¤ Two graphs may have a same degree sequence with different graphical representation.
¤ A sequence is said to be graphical if there exists a simple graph G such that the given sequence
is the degree sequence of G.
Problem 1.3.1: Show that the degree of a vertex of a simple graph G of order n cannot exceed n – 1.

Solution: Let v be a vertex of G. Since G is simple, no multiple edges or loops are allowed in G.
Thus v can be adjacent to at most all the remaining n – 1 vertices of G. Hence v may have maximum
degree n – 1 in G.

¤ Thus for every vertex v in a simple graph G, 0 ≤ deg (v) ≤ n – 1.

Theorem 1.3.1: (Euler) Let G be a (p, q) – graph. Then  deg(v)  2q .

vV (G)

Proof: Let v1, v2, ........ , vp be the vertices of a graph G. Then,

p p


vV (G)
deg(v)   deg(vi )   (number of edges adjacent to vi in G)
i1 i1
- - - - - - - - (1)

Since each edge is adjacent to exactly two vertices of G, while taking the sum in the right hand side
of the equation (1), each edge counts twice (i.e. if e = vivj then e counts for the degree of the vertex vi
and for the degree of the vertex vj) and every edge of G contributes to the degree of a vertex of G.
Hence the right hand side of (1) is equal to 2q, where q is the number of edges of G.
Hence  deg(v)  2q 
vV (G)

Note: The above theorem is also known as hand shaking property.

Corollary 1.3.2: Total number of odd degree vertices in a graph is always even.
Proof: Let v1, v2, . . . . , vp be the vertices of a graph G in which v1, v2, . . . . , vk be odd degree
p

vertices. Then by the Theorem 1.3.1,  deg(v )  2q . That is,

i1
i

k p

 deg(v )   deg(v )  2q  even number

i1
i
ik 1
i

Page 7
 k p

  deg(vi )  (even number)   deg(v ) i

i1 ik 1

Since each of the vertices vk+1, vk+2, . . . . , vp are of even degree, therefore we get,
k p

 deg(v )  (even number)   (even number)  even number

i1
i
ik 1

This implies that, the sum of degrees of all odd degree vertices is even. Hence the number of odd
degree vertices in G is even. 

Problem 1.3.2: Show that there exist no simple graphs corresponding to following degree sequences
(i) 4, 3, 2, 2, 0 (ii) 3, 2, 1, 1 (iii) 6, 5, 4, 3, 3, 2 (iv) 6, 4, 2, 2

Solution: In (i), (ii) and (iii), there are odd numbers of odd degree vertices. Hence there exist no
graphs corresponding to these degree sequences. In (iv), number of vertices in the graph is four and
the maximum degree of the vertex is six, which is not possible as the maximum degree cannot exceed
one less than the number of vertices.

Problem 1.3.3: For a graph with n vertices and m edges. If δ is minimum and Δ is maximum of
2m
degree of vertices, then show that    
n
Solution: Let d1, d2 , dn be the degrees of the vertices of the graph with   min{d1, d2, dn}and

  max{d1, d2, d n }.

Then,   d1,   d2 ,   dn  n  d1  d2   dn and by Hand shaking property,

d1  d2   dn 2m , therefore n  2m   2m/n. (Proof of other part is left to the reader)

In-degree and Out-Degree:

Let v be a vertex in a directed graph G, the number of edges for which v is a terminal vertex is called
in-degree of v and the number of edges for which v is a initial vertex is called out-degree of v.

¤ The out-degree of v is denoted by d  (v) and in-degree of v is denoted by d  (v)

Theorem 1.3.3: In every directed graph G, the sum of the out-degree of all vertices is equal to the
sum of in-degree of all vertices, each sum being equal to the number of edges in G.

Proof: Suppose G has n vertices 𝑣1 , 𝑣2 , … , 𝑣𝑛 and m edges. Let 𝑟1 , 𝑟2 , … , 𝑟𝑛 be the number of edges
going out of 𝑣1 , 𝑣2 , … , 𝑣𝑛 respectively. Then 𝑑 + (𝑣1 ) = 𝑟1 , 𝑑 + (𝑣2 ) = 𝑟2 , … , 𝑑 + (𝑣𝑛 ) = 𝑟𝑛 . Every edge
terminates at some vertex and since there are 𝑚 edges, we have 𝑟1 + 𝑟2 + ⋯ + 𝑟𝑛 = 𝑚 and hence
𝑑 + (𝑣1 ) + 𝑑+ (𝑣2 ) + ⋯ + 𝑑+ (𝑣𝑛 ) = 𝑚. Similarly one can prove 𝑑 − (𝑣1 ) + 𝑑 − (𝑣2 ) + ⋯ + 𝑑 − (𝑣𝑛 ) = 𝑚.

Page 8
 Problem1.3.4: Let G be a digraph with an odd number of vertices. Prove that if each vertex of G has
an odd out-degree, then G has odd number of vertices with odd in-degree.
Solution: Let 𝑣1 , 𝑣2 , … , 𝑣𝑛 be n vertices of 𝐺 , where n is odd. Also let 𝑚 be the number of edges in
𝐺. Then we have 𝑑 + (𝑣1 ) + 𝑑+ (𝑣2 ) + ⋯ + 𝑑 + (𝑣𝑛 ) = 𝑚.

Since each term in the left hand side is odd and there are odd numbers of terms in the left hand side,
m is odd. Let k be the number of vertices of odd in-degree. Then 𝑛 − 𝑘 be the number of vertices of
even in-degree. Without loss of generality let us take 𝑣1 , 𝑣2 , … , 𝑣𝑘 to be the vertices with odd in-
degree and 𝑣𝑘+1 , 𝑣𝑘+2 , … , 𝑣𝑛 to be the vertices with even in-degree. Then we have

𝑘 𝑛

𝑑 − (𝑣1 ) + 𝑑− (𝑣2 ) + ⋯ + 𝑑 − (𝑣𝑛 ) = ∑ 𝑑 − (𝑣𝑖 ) + ∑ 𝑑 − (𝑣𝑖 ) = 𝑚

𝑖=1 𝑖=𝑘+1

This implies, ∑𝑘𝑖=1 𝑑 − (𝑣𝑖 ) = 𝑚 − ∑𝑛𝑖=𝑘+1 𝑑 − (𝑣𝑖 ) …………..(1)

Since m is odd and 𝑑− (𝑣𝑖 ) is even for 𝑘 < 𝑖 ≤ 𝑛, the right hand side of (1) is odd. Thus ∑𝑘𝑖=1 𝑑− (𝑣𝑖 ) is
odd. But each of 𝑑− (𝑣𝑖 ) is odd for 1 ≤ 𝑖 ≤ 𝑘, therefore the number of terms in the left hand side of (1)
must be odd. Thus there is odd number of odd in-degree vertices in 𝐺

1.4. Some Special Graphs:

a) Regular graphs: A graph G is said to be regular graph of regularity ‘r’ if deg (vi) = r for all vi 
V(G). In this case G is also called r-regular graph.

Note: A 3-regular graph is often called a cubic graph.

Remark 1.4.1: Every cubic graph has even number of points. (Follows from the corollary1.3.2)
The following are some examples of cubic graphs on 10 vertices.

Note: The third graph in the above example is called Petersen Graph. It is a small graph that serves
as a useful example and counter example for many problems in graph theory.

b) Complete graph: A full graph or a complete graph on n vertices, denoted by Kn, it is a simple

Page 9
 graph in which every pair of vertices are adjacent. Thus size of the graph Kn is nC2 .

¤ A graph on n vertices is a complete graph if and only if it is a regular graph of regularity n – 1.

¤ The graph K1 is called trivial graph.

The following are the examples of complete graphs up to the order five.

Note: The graph K5 is called Kuratowski’s first graph (This is a non planar graph of smallest order.
The interested one can learn what is a planar graph and importance of Kuratowski’s graphs in the
detection of planarity of a graph.)

a) Null graph: A graph of order n and size zero is called a null graph or a totally disconnected
graph, and is denoted by K n . Thus E  K n    .

¤ Vertex set of a graph is always nonempty (follows by definition)

¤ Every vertex of a null graph is an isolated vertex. Further a graph of order n is a null graph if
and only if it is a regular graph of regularity zero.

b) Bipartite graph: A graph G (V, E) is said to be bipartite if the vertex set V of the graph G can be
partitioned into two nonempty subsets V1 and V2 such that no two vertices in the same set (i.e. in V1
or V2) are adjacent in G (or equivalently, every edge in G has one end vertex in V1 and the other end
vertex in V2).
The graph G1 in the following figure is a bipartite graph, where V1 {a, c, e} and V2 {b, d, f }
form partition of vertex set V(G1) (observe that every edge has one end vertex in V1 and the other in
V2. While the graph G2 in the following example is not bipartite (prove!).

Page 10
 a b
c

d
f e

Example of bipartite graph G1

Example of graph G2 which is not

Problem 1.4.1: Show that the maximum number of edges in a bipartite graph of order 2n is n2.
Solution: Let G(V, E) be a bipartite graph with 2n vertices and m edges. Let V1 and V2 be vertex
partition of G with V1  n1 and V2  n2 . Then n1  n2  2n . Since G is bipartite no two verities in V1,

as well as two verities in V2 are adjacent, hence the maximum number of edges possible in G is n1n2
The maximum possible value of n1n2 satisfying 𝑛1 + 𝑛2  2n is n2.
(i.e. when 𝑛1 = 𝑛2= 𝑛)
1 2 1 2
Thus, maximum possible number of edges in G
c) Complete bipartite graph: A bipartite graph G with vertex partition V1 and V2 is said to be
complete bipartite graph, if every vertex in V1 is adjacent to every vertex in V2. A complete bipartite
graph with vertex partition V1 and V2 having V1  m and V2  n is denoted by Km,n.

¤ If V1 and V2 are partition of vertex set of Km,n, then every vertex in V1 is adjacent to every
vertex in V2
¤ The graph K1,n is called a star.

Following are some examples of complete bipartite graphs.

Page 11
 K2,4 K3,3 K1,5

NOTE:

 Order of 𝐾𝑚,𝑛 is m + n and the size is mn.

 The graph K3,3 is called Kuratowski’s second graph (This is a non planar graph of smallest
size).

1.5. Subgraphs

Graph G1 = (V1, E1) is said to be a subgraph of the graph G = (V, E) if V1  V and E1  E. (i.e. A
subgraph G1 of a graph G is a graph whose vertex set is a subset of that of G, and whose adjacency
relation is a subset of that of G.) If G1 is subgraph of G, then G is called a supergraph of G1

For the graph G represented in the Figure 1.5.1, the graphs H1, H2, H3, H4 and H5 are different
subgraphs of G.

Note:
¤ A subgraph is a graph which is a part of another graph.
¤ Any graph isomorphic to a subgraph of a graph G is also called a subgraph of G. (We define
isomorphism of two graphs in the next section of this unit)
¤ Every graph is a subgraph of itself.
¤ Every simple graph of n vertices is a subgraph of the complete graph Kn.
¤ If G1 is a subgraph of a graph G2, and G2 is a subgraph of a graph G, then G1 is a subgraph of
the graph G.

Page 12
 ¤ A single vertex in a graph G is a subgraph of G.
¤ A single edge in a graph G, together with its end vertices, is a subgraph of G.

v1
G: H2: v2
v1 v2 v2
H1:

v3 v3
v5 v4
v5 v4 v4
v1
H3: v1 v2 H4: v1 v2 H5:

v4
v3 v3
v5
v5 v4 v5 v4

Special Types of Subgraphs:

1. Spanning subgraph: A subgraph G1 = (V1, E1) is called a spanning subgraph of a graph
G = (V, E), if V1 = V. (i.e. if G1 is a spanning subgraph of G then vertex set of G1 is same as vertex
set of G.
In the Figure 1.5.1, H1 and H2 are subgraphs of G but they are not spanning subgraphs of G. The
graphs H3 and H4 spanning subgraphs of G.

2. Induced subgraph: A subgraph G1 = (V1, E1) of a graph G = (V, E) is said to be induced

subgraph of G, induced by V1, if it contains all the edges of G which are incident on V1.

In other words, G1 = (V1, E1) is an induced subgraph of G if it has all the edges that appear in G over
the same vertex set V1.
In the Figure 1.5.1, H1 is an induced subgraph of G. The graphs H2, H3 and H4 are not induced
subgraphs of G. (Observe H1 is induced by vertex set V1 = {v2, v3, v4}, a subset of V).

3. Edge-disjoint and vertex disjoint Subgraphs: Let G be any graph and G1 & G2 two subgraphs
of G, then
• G1 & G2 are said to be edge-disjoint if they do not have any common edge.
• G1 & G2 are said to be vertex-disjoint if they do not have any common vertex.

Page 13
In the Figure 1.5.1, H1 and H5 are edge disjoint subgraphs of graph G, but they are not vertex disjoint.
Note – Two vertex disjoint subgraphs are always edge disjoint subgraphs, converse need not true.

1.6. Isomorphism of Graphs

Let G1 and G2 be any two graphs. Then a bijective function (both one-one and onto)
f :V (G1) V (G2 ) is called an isomorphism if it preserves adjacency as well as non-adjacency of the
vertices of the graphs G1 and G2. Two graphs G1 and G2 are said to be isomorphic to each other if
there exists an isomorphism between them. If G1 and G2 are said to be isomorphic then we write
G1  G2 and read as G1 is isomorphic to G2.
On the other hand if G1  G2 , then there exists a function f :V (G1) V (G2 ) with the following
property,
i) f (x)  f ( y)  x  y for all x, y V (G1)

ii) For each y V (G2 ) there exists x V (G1) such that f (x)  y

iii) x, y are adjacent in G1 if and only if f (x), f ( y) are adjacent in G2

Consider the following graphs
a b x
1 G3:
G: G:
2 2
1 z
y
3
d c
4 w
1
1 2
G4: G5: G6:

3
4 3 1 2 3 4
4 2
In the above example V(G1 ) ={1, 2, 3, 4} , V(G2) = {a, b, c, d} , E(G1) = { (1,2) , (2,3) , (3,4) } and
E(G2) = {(a, b), (b, d), (d, c)}. Define a function f:V (G1 ) V (G2 ) define as f (1) = a, f (2) = b, f
(3) = d and f (4) = c, then f is clearly one-one and onto, further,
{1, 2} E (G1) and {f (1), f (2)} = {a, b} E (G2)
{2, 3} E (G1) and {f (2), f (3)} = {b, d} E (G2)
{3, 4} E (G1) and {f (3), f (4)} = {d, c} E (G2)

Page 14
and
{1, 3}  E (G1) and {f (1), f (2)} = {a, b}  E (G2)
{1, 4}  E (G1) and {f (1), f (4)} = {a, c}  E (G2)
{2 , 4}  E (G1) and {f (2), f (4)} = {b, c}  E (G2).

Hence f preserves adjacency as well as non-adjacency of the vertices. Therefore, G1 and G2 are
isomorphic. The graphs G1 and G3 , G2 and G3 are non-isomorphic, because their size are different
(we cannot establish an isomorphism between the vertices by preserving the adjacency). The graph
G4 , G5 and G6 are isomorphic to each other.

Note: If two graphs G1 and G2 are isomorphic to each other, then the following hold;

¤ Both the graphs G1 and G2 have same number of vertices.

¤ Both the graphs G1 and G2 have same number of edges.
¤ Degree sequences of the both the graphs are same.

But the converse need not be true in general. As a counter example we show below in figure the
existence of two non-isomorphic graphs satisfying all the above three conditions.

G1: G2:

Note: Isomorphism is an equivalence relation on set of all simple graphs.

An invariant of a graph G is a number associated with G which has the same value for any graph
isomorphic to G. Thus the numbers p and q are certainly invariants. A complete set of invariants
determines a graph up to isomorphism. For example, the numbers p and q constitute such a set for all
graphs with less than four points. No decent complete set of invariants for a graph is known.

Finding complete set of graph invariants is still an open problem in graph theory. Many researchers
got partial success but for graphs of larger order finding complete set of invariants is an NP-complete
problem. The learners are advised not to try this problem at this stage.

1.7. Summary

A graph G = (V, E) consists of a non-empty set of objects V whose elements are called vertices and
another set E whose elements are called edges, such that each edge ek  E is identified with an
unordered pair {vi, vj} of elements of V. A graph is represented by means of diagram. If the edges are

Page 15
identified with orientation, then the graph is called digraph. We classify the graphs as simple graph,
multigraph, pseudo graph.

The number of edges incident on a vertex counting self-loop twice is a degree of the vertex. The sum
of degree of all vertices of G is equal to 2 times the number of edges in G (This result is also known
as first theorem of graph theory). If the degrees of all the vertices are same then it is called regular
graph. If every pair of vertices are adjacent then it is called complete graph.

Graph G1 = (V1, E1) is said to be a subgraph of the graph G = (V, E) if V1  V and E1  E. If G1 is a

subgraph of G then the graph G is super graph of G1. A subgraph G1 containing all vertices of G is
called spanning subgraph of G. Two identical graphs are called isomorphic to each other and an
invariant of a graph G is a number associated with G which has the same value for any graph
isomorphic to G.

1.8. Keywords
Graph, digraph, subgraph, complete graph, bipartite graph, regular graph, graph isomorphism
1.9. Exercises
1. Show that there is no graph 12 vertices and 28 edges where,
a) The degree of each vertex is either 3 or 4.
b) The degree of each vertex is either 3 or 6.

2. If be connected undirected graph what is largest value of , if and

for all
3. Define directed graph and an undirected graph.
a) Let be undirected graph with and if and no loops, prove that
.
b) State the corresponding inequality for the case when G is directed.

4. State and prove Hand shaking property. Hence prove that there is no graph with odd number of
odd degree vertices.

5. Show that every simple graph of order ≥2 must have at least two vertices of the same degree.

6. Let G be graph with n vertices and m edges and let k be the smallest positive integer such that
2m
k . Prove that G has a vertex of degree at least k.
n

Page 16
7. Let D be a directed graph with n vertices. If the underlying graph of D is Kn, then prove that

 d  (v )   d  (v )

2 2
i i .
vV vV

8. If a bipartite graph G(V1, V2 , E) G is regular, then show that |𝑉1 | = |𝑉2 |.

9. Show that not possible to have a set of seven persons such that each person in the set knows
exactly three other persons in the set.
10. Define Isomorphism of two graphs. Prove that the following graphs are isomorphic.

* Marked problems are thought provoking.

1.10. References:
1. F. Harary, Graph Theory, Addison-Wesley, 1969
2. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science,
PHI, 2011.
3. B. Sooryanarayana and G. K. Ranganath, Text book of graph theory, S. Chand and Co.
New Delhi.
4. D.B. West, Introduction to Graph theory, Prentice Hall India 2001
5. G. Chartrand and L. Lisniak, Graphs and Digraphs, Wordsworth, [Link],
California, 1986.

Page 17
 UNIT– 2

WALKS AND CONNECTEDNESS

Structure:

2.0. Objectives

2.1. Introduction

2.2. Walks and Their Classifications

2.3. Connected and Disconnected graphs

2.4. Distance in Graphs

2.5. Summary

2.6. Keywords

2.7. Exercises

2.8. References

Page 18
2.0. Objectives
The objective of this unit is to make the learners conversant on –
 Terminologies like walk, path, cycle, circuit in a graph
 Connected and disconnected graphs
 Distance in graphs

2.1. Introduction

In this unit we introduce additional concepts of graph theory which are not discussed in the previous
unit. These concepts, such as paths, circuits, deal mainly with the nature of connectivity in graphs.
We extend the conversation to introduce new graph invariants like radius, diameter, girth and to
discuss their properties.

2.2. Walks and Their Classifications

Walk - A sequence u, v1, v2, …, vn – 1, v is called u-v walk of length n, where vi is adjacent to vi+1. A
walk that begins and ends with the same vertex is called a closed walk. Otherwise it an open walk.

Trail – An open walk in which no edge appears more than once is called a trail.

Circuit - A closed walk in which no edge appears more than once is called a Circuit.

Path - An open walk in which no vertex appears more than once is called a Path.

Cycle - A closed walk in which no vertex other than initial and end vertex, appears more than once is
called a Cycle.

Example: Consider the graph G represented by the following diagram.

v6
G:
v1

v2 v5
v4
v3

In the above graph

 v1, v2, v3, v1, v6, v3, v2, – Is a walk (but not a trail, not a path).
 v1, v2, v3, v1, v6, v3, v4, v5 – Is a trail (also a walk but not a path).
 v1, v2, v3, v6, v4, v5 – Is a path (also a trail and also a walk).

Page 19
  v1, v2, v3, v1 – Is a cycle (also a circuit).
 v1, v2, v3, v1, v6, v3, v4, v6, v1 – Is a circuit (but not a cycle).
 v1, v2, v3, v1, v6, v2, v4, v5 – Is not a walk.

Note:
¤ The length of a walk is the number of edges in a walk [or1 less than number of vertices]. If the
length of walk is odd, then it is called an odd walk and if the length of walk is even, then it is
called an even walk.
¤ The length of a path is the number of edges in a path [or 1 less number of vertices]
¤ The length of a cycle is the number of edges in a cycle [or number of distinct vertices]. If the
length of cycle is odd, then it is called an odd cycle and if the length of cycle is even, then it is
called an even cycle.
¤ Every path is a trail but converse is not true.
¤ Every trail is a walk but converse is not true.
¤ Every cycle is a circuit but converse is not true.

Some special graphs:

a) Path: A path on n vertices is denoted by Pn , it is a graph in which if V (Pn ) {v1, v2 , vn} is the

vertex set of Pn , then vi vj is an edge in Pn if and only if i  j  1. (or any graph isomorphic to it).

P2 P3 P4

P5 Pn
¤ The path Pn is defined for all integers n  2 . The graphs P2 and K2 are isomorphic.

Page 20
b) Cycle: A cycle on n vertices is denoted by Cn , it is a graph in which if V (Pn ) {v1, v2 , vn} is

the vertex set of Cn , then vi vj is an edge in Cn if and only if i  j  1 or i  j  n 1 (or any

graph isomorphic to it).

C3 C4 C5 C6
¤ Cn is a simple graph for all integer n  3 . The graphs C3 and K3 are isomorphic.

c) Wheel: A wheel on n+1 vertices is denoted by W1,n , it is a graph in which if

V (W1,n ) {v, v1, v2 , vn} is the vertex set of W1,n , then vi vj is an edge in W1,n if and only if

i  j  1 or i  j  n 1 and v is adjacent to vi for all i = 1, 2, 3, . . . , n.

W1,3 W1,4 W1,5

¤ W1,n is defined for all integer n  3 . The graphs W1,3 and K4 are isomorphic.

¤ The vertex v of degree n in W1,n is called central vertex and all the remaining vertices (of

degree 3) are called rim vertices.

¤ The number of edges in W1,n is 2n.

Theorem 2.2.1: Every u– v walk in graph contains a u– v path.

Proof: Let W be a u-v walk in a graph G. If W is closed, the result is trivial. Let W: u = u0, u1 , u2 , .
. . , uk = v be an open u-v walk of a graph G. (A vertex may have received more than one label.) If no
vertex of G occurs in W more than once, then W is a u-v path. Otherwise, there are vertices of G that
occur in W twice or more. Let i and j be distinct positive integers, with i < j say, such that ui = uj. If
the terms ui , ui+1 , . . . , uj-1 are deleted from W, a u-v walk W1 is obtained having fewer terms than
that of W. If there is no repetition of vertices in W1, then W1 is a u-v path. If this is not the case, we
continue the above procedure until finally arriving at a u-v walk that is a u-v path.

Page 21
2.3. Connected and disconnected Graphs

Lt G = (V, E) be any graph and u, v be vertices of G then u and v are said to be connected if there is a
u–v path in G. A graph in which every pair of vertices are connected is called a connected graph. In
other words, a graph G is said to be connected if there exist a path between every pair of vertices in
G.

Examples:

v6 v6
G2 : v7
G1 :
v5 v1 v5
v1

v4 v2 v4
v2
v3 v3

In the above examples graph G1 is connected the graph G2 is disconnected.

Component: Maximal connected sub graph of G is called a component of G. In the above example G2
there are two components they are
v7
v6
v1
v5
H1:
And H2:

v2
v3 v4
Note: Connected graph has only one component and a graph G is disconnected if and only if it has
more than one component.
Some results on connected and disconnected graphs
Theorem 2.3.1: A graph G is disconnected if and only if its vertex set V can be partitioned into two
nonempty disjoint subsets V1 and V2 such that there exists no edge in G whose one end vertex is in
subset V1 and the other in subset V2.
Proof: Suppose that such a partitioning exists. Consider two arbitrary vertices a and b of G. such that
a V1 and bV2. No path can exist between vertices a and b. otherwise there would be at least one
edge whose one end vertex would be in V1 and the other in V2. Hence if a partition exists, G is not
connected.

Page 22
Conversely, let G be a disconnected graph. Consider a vertex a in G. Let V1 be the set of all vertices
that are joined by paths to a. Since G is disconnected, V1 does not include all vertices of G. The
remaining vertices will form a (nonempty) set V2. No vertex in V1 is joined to any in V2 by an edge.
Hence the partition.

Theorem 2.3.2: If a graph (connected or disconnected) has exactly two vertices of odd degree, there
must be a path joining these two vertices.
Proof: Let G be a graph with all even vertices except vertices v1 and v2, which are odd. From
previous theorem which holds for every graph and therefore for every component of a disconnected
graph, no graph can have an odd number of odd vertices. Therefore, in graph G, v1 and v2 by must
belong to the same component, and hence must have a path between them.

Theorem 2.3.3: A simple graph G with n vertices and k components can have at most
(n  k)(n  k 1)
edges.
2
Proof: Let n , n , , n be the number of vertices in first, second … kth component of graph G
1 2 k

respectively. A component with ni number of vertices, being a subgraph of simple graph, can have at
𝑛 (𝑛 −1)
most 𝑖 2𝑖 edges.
𝑛𝑖 (𝑛𝑖 −1) 𝑛𝑖2 −𝑛𝑖 2
Number of edges in 𝐺 ≤ ∑𝑘𝑖=1 = ∑𝑘𝑖=1 = 1/2 ( ∑𝑘𝑖=1 𝑛𝑖 − ∑𝑘𝑖=1 𝑛𝑖 )
2 2

We have 𝑛 i  n1  n2  … nk  n --------- (2)

 (n1 1)  (n2 1)   (nk 1)  n  k

Squaring on both the sides we get, (n1 1)2  (n2 1)2   (nk 1)2  S  (n  k)2, with S ≥ 0.

k
Simplifying we get  n 2  n2 (k 1)(2n  k)
i1
i --------- (3)

Substituting (2) and (3) in (1) and simplifying we get,

(n  k) (n  k  1)
Number of edges in G ≤
2
1
Corollary 2.3.4: If m  (n 1)(n  2) , then a simple graph G with n vertices and m edges is
2
connected.

Page 23
Proof: Suppose the graph G is disconnected. Then it has at least two components and by Theorem
1 1
2.3.3, m  (n  k)(n  k 1) for all k ≥ 2. For k = 2 m  (n 1)(n  2) , A contradiction to the
2 2
1
given data that m  (n 1)(n  2) . Hence the graph G must be connected.
2

Theorem 2.3.5: A connected graph G with n vertices has at least n – 1 edges.

Proof: Given that the graph G is connected with n vertices. For n = 1 the only simple graph is K1,
result holds trivially. Let n ≥ 2. We prove this result by induction on n, number of vertices.
Suppose n = 2, i.e. there are 2 vertices in the graph and since the graph is connected, there must be at
least one edge joining these vertices. Hence the result holds for n = 2.
Assume that the is true for all connected graphs with n = k vertices, (k is a positive integer k ≥ 2)

i.e. “A connected graph G with k vertices has at least k – 1 edges”.

Now consider a connected graph G with k + 1 vertices. Choose a vertex v of this graph such that
removal of v does not disconnect the graph. (Removal of a vertex v is a subgraph of G obtained from
deleting v and all edges incident on v) Since G is connected, deg (v) ≥ 1.

Consider a graph G – v. It has k vertices and is connected. By inductive assumption G – v has at least
k – 1 edges. Thus G has at least k edges (Since deg (v) ≥ 1). Hence result holds for n = k + 1. Thus,
by principle of induction result hold for all connected graphs with n vertices.

Note: A bipartite graph (or bigraph) G is a graph whose point set V can be partitioned into two
subsets V1 and V2 such that every line of G joins V1 with V2.

Theorem 2.3.6: A graph is bipartite if and only if all its cycles are even.

Proof: If G is a bipartite, then its point set V can be partitioned into two subsets V1 and V2 so that
every line of G joins a point of V1 with a point of V2. Thus every cycle v1, v2, . . . , vn v1 in G
necessarily has its oddly subscripted points in V1 say and the others in V2 so that its length n is even.

For the converse, we assume, without loss of generality, that G is connected (for otherwise we can
consider the components of G separately). Take any point v1 є V and let V1 consist of v1 and all pints
at even distance from v1. While V2 = V – V1. Since all the cycles of G are even, every line of G joins a
point of V1 with a point of V2. For suppose there is a line uv joining two points of V1. Then the union
of geodesics from v1 to v and from v1 to u together with the line uv contains an odd cycle, a
Contradiction.

Page 24
2.4. Distances in Graphs

Let G be a connected graph and u,v be any two vertices of G. Then among all the uv-paths, the one
having minimum length is called a shortest uv-path. A Shortest uv-path is also called a geodesic. The
distance d (u, v) between two vertices u and v in G is the length of a shortest path joining them if any;
otherwise d (u, v) = ∞.

Remark 2.4.1: In a connected graph G, distance is a metric; that is, for all u, v, and w  G
 d (u, v) > 0, with d (u, v) = 0 if and only if u = v.
 d (u, v) = d (v, u).
 d (u, v) + d (v, w) ≥ d (u, w).
Definition 2.4.1: The girth of a graph G, denoted g(G), is the length of a shortest cycle (if any) in G;
the circumference c(G) the length of any longest cycle.

¤ Note that these terms are undefined if G has no cycles.

Definition 2.4.2: The eccentricity e(v) of a vertex v in a connected graph G is defined as

max{d(u, v) : u, v V (G)}. The radius rad (G) is the minimum eccentricity of the vertices. Note that
the maximum eccentricity is the diameter of G and denoted by diam (G). A vertex v is a central
vertex if e (v) = rad (G), and the center of G is the set of all central points.

Example: Consider the graph G represented by the following diagram.

a b c d

i
i h g f
G

For the graph G in the above example e (a) = 4, e (b) = 3, e (c) = 2, e (d) = 3, e (i) = 4, e ( f ) = 3, e
(g) = 3, e (h) = 4, e (i) = 3. rad (G) = 2 and diam (G) = 4 and the vertex c is center of G

¤ For a complete graph Kn , rad(Kn )  diam(Kn )  1 and every vertex of Kn is a central

vertex. Also g(Kn )  3 and c(Kn )  n
𝑛
¤ For a cycle 𝐶𝑛 〖𝑟𝑎𝑑(𝐶〗𝑛 ) = 𝑑𝑖𝑎𝑚(𝐶𝑛 ) = ⌊ 2⌋ and 𝑔(𝐶𝑛 ) = 𝑐(𝐶𝑛 ) = 𝑛

¤ For a wheel W1,n , rad (W1,n )  1, diam(W1,n )  2 , g(W1,n )  3 and c(W1,n )  n

Page 25
 Theorem 2.4.1: For any connected graph G, rad (G) ≤ diam (G) ≤ 2 rad (G).

Proof: The inequality rad (G) ≤ diam (G) is a direct consequence of the definitions. In order to
verify the second inequality, select vertices u and v in G such that d(u ,v) = diam(G). Furthermore, let
w be a central vertex of G. Since distance function d is a metric on V(G),
d (u ,v) ≤ d ( u, w) + d(w ,v)
≤ rad (G) + rad (G)
= 2 rad (G).
Theorem 2.4.1 gives a lower bound (viz, rad (G)) for the diameter of a connected graph G as well as
an upper bound (viz, 2rad (G)). This is the first of many results we shall encounter for which a
question of “Sharpness” is involved. In other words, just how good is this result? Ordinarily, there
are many interpretations of such a question. We shall consider some possible interpretations in the
case of the upper bound.
Certainly, the upper bound in Theorem 2.4.1 would not be considered sharp if dram (G) < 2 rad (G)
for every graph G. However, it would be considered sharp indeed if diam (G) = 2 rad (G) for many
graphs G. In the letter case, we would have a formula, not just a bound. Actually, there are graphs G
for which diam (G) < 2 rad (G) and graphs H for which diam (H) = 2 rad (H).

Note: The concept of distance in graphs can be generalized in a most natural manner. By a weighted
graph, we mean a graph in which each edge e is assigned a positive real number, called the weight of
e, and denoted by w (e). The length of a path P in a weighted graph G is the sum of the weights of the
edges of P. For connected vertices u and v of G, the distance d (u, v) between u and v is the minimum
of the lengths of the u – v paths of G.

Remark 2.4.1: If each edge of a weighted G has weight 1, then G can be regarded as a graph (viz,
non weighted graph).

Definition 2.4.3: The square G2 of a graph G has V (G2) = V (G) with u, v adjacent in G2 whenever d
(u, v) < 2 in G. The powers G3, G4, . . . of G are defined similarly.

Example:

𝑃𝟓𝟐
𝐶𝟓𝟐

Page 26
2.5. Summary

A sequence of vertices in which every pair of consecutive vertices are adjacent is a walk in the graph.
A walk in which no two vertices repeat is called a path. The concept is used to develop
connectedness in graph. Connectedness plays a very important role in graph theory and its
applications. This unit gives a base to solve famous problems like Chinese Postman problem and
Salesman problems, which we are going to discuss in the next unit.

The distance d (u, v) between two vertices u and v in G is the length of a shortest path joining them.
Distance in graph is a metric and it introduces a new graph invariants girth and circumference. The
powers G2, G3, G4, . . . of G are defined using the distance concept.

2.6. Key Words

Path, Cycle, Circuit, Connected Graphs, Radius, Girth, Circumference, Power Graphs.
2.7. Exercises

1. If G is simple graph of order n, with di as the degree of vertex vi for i = 1, 2, 3, . . . n. Find the
number of paths of length 2 in G.

2. If G is simple graph of order 8, with degree sequence 1, 2, 2, 2, 3, 4, 4, 6. Then find the

number of paths of length 2 in G.

3. If G is simple graph in which every vertex has degree at least k. Prove that G contains a path
of length at least k.

4. If G is simple graph with no cycles then prove that G has length at least one pendant vertex.

5. If G is simple graph in which every vertex has degree at least 2. Prove that G contains a
cycle.

6. If there exist two different paths between two given vertices of a graph G, then prove that G
has a cycle in it.

7. Prove that in a graph there is a u-v trail if and only if there is a u-v path.

8. If G is a simple connected graph with n vertices in which the degree of every vertex is at least
n 1
, then prove that G is connected.
2

9. Prove that a connected graph G remains connected after removing an edge e from G if and
only if e is an edge of some cycle in G.

10. Prove that a connected graph of order n and size m has at least n – m components.

Page 27
 11. Let n and m be positive integers such that n ≤ m ≤ 2n. Prove that there exists a graph G such
that rad (G) = n and diam (G) = m.

12. Find out the centre of the following graphs. Also calculate the radius of each graph.

13. Give two different graphs G1 and G2 such that :

a) rad (G) = diam (G)
b) diam (G) = 2 rad (G)
c) rad (G) < diam (G)
d) diam (G) < 2 rad (G)

14. Prove that for a connected graph G the distance function d (u, v) defined on set of all vertices
of G is a matric. [i.e. d (u, v) ≥ 0 and d (u, v) = 0 if and only if u = v; d (u, v) = d (v, u) ; and
d (u, v) ≤ d (v, w) + d (w, v) for all u, v, w V(G).]

15. Prove that connectedness of vertices is an equivalence relation on the set of vertices of G.

2.8. References:

1. F. Harary, Graph Theory, Addison-Wesley, 1969

2. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science,
PHI, 2011.
3. B. Sooryanarayana and G. K. Ranganath, Text book of graph theory, S. Chand and Co.
New Delhi.
4. D.B. West, Introduction to Graph theory, Prentice Hall India 2001
5. G. Chartrand and L. Lisniak, Graphs and Digraphs, Wordsworth, [Link],
California, 1986.

Page 28
 UNIT – 3

THE PROBLEM OF RAMSEY, EXTREMAL GRAPHS, INTERSECTION GRAPHS

Structure:

3.0 Objectives

3.1 Introduction

3.2 The Problem of Ramsey

3.3 Extremal Graphs

3.4 Intersection Graphs

3.5 Excursion

3.6 Summary

3.7 Keywords

3.8 Exercise

3.9 References

Page 29
 3.0 Objectives

The objective of this unit is to make the learners conversant on;

 The Problem of Ramsey

 Extremal Graphs

 Intersection Graphs

 Excursion (Special class of Intersection Graphs)

3.1 Introduction

In graph theory, the Ramsey number is the minimum number of vertices, 𝑣 = 𝑅(𝑚, 𝑛) such that all
undirected simple graphs of order v, contain a clique of order m, or an independent set of order n.
Ramsey’s Theorem states that such a number exists for all m and n. A graph that is an optimal
solution to such an optimization problem is called an extremal graph, and extremal graphs are
important objects of study in extremal graph theory. A graph 𝐺 = (𝑉, 𝐸) is called an intersection
graph for a finite family F of a non-empty set if there is a one-to-one correspondence between F
and V such that two sets in F have non-empty intersection if and only if their corresponding vertices
in V are adjacent.

3.2. THE PROBLEM OF RAMSEY

A puzzle which has become quite well known may be stated in the following form:

Prove that at any party with six people, there are three mutual acquaintances or three mutual non
acquaintances.

Figure. 3.2.1

Page 30
This situation may be represented by a graph G with six points standing for people, in which
adjacency indicate acquaintance. Then the problem is to demonstrate that G has three mutually
adjacent points or three mutually nonadjacent ones. The complement 𝐺 of a graph G also has V(G)
as its point set, but two points are adjacent in 𝐺 if and only if they are not adjacent in G. In Fig
3.2.1, G has no triangles, while 𝐺 consists of exactly two triangles. A self-complementary graph is
isomorphic with its complement. (See Figure 3.2.2.)

Figure 3.2.2. The smallest nontrivial self-complementary graphs

𝑝
The complete graph 𝑘𝑝 has every pair of its p points adjacent .Thus 𝑘𝑝 has ( ) lines and is regular
2
of degree 𝑝 − 1. As we have seen, 𝐾3 is called a triangle. The graphs 𝑘𝑝 are totally disconnected
and are regular of degree 0.

Theorem 3.2.1: For any graph 𝐺 with six points, G or 𝐺 contains a triangle.

Proof: Let v be a point of a graph G with six points. Since v is adjacent either in 𝐺 or in 𝐺 to the
other five points of 𝐺, we can assume without loss of generality that there are three points 𝑢1, 𝑢2, 𝑢3
adjacent to 𝑣 in 𝐺. If any two of these points are adjacent, then they are two points of a triangle
whose third point is 𝑣. If no two of them are adjacent in 𝐺, then 𝑢1, , 𝑢2 and 𝑢3 are the points of a
triangle in 𝐺.

The result of the above Theorem suggests the general question: What is the smallest integer r(m,
n) such that every graph with r(m, n) points contains 𝑘𝑚 𝑜𝑟 𝑘𝑛 ?

The values r(m, n) are called Ramsey numbers. Of course r(m, n)= r(n, m) The determination of the
Ramsey numbers is an unsolved problem. A simple bound was found by Erdös and Szekeres.

𝑚+𝑛−2
𝑟(𝑚, 𝑛) ≤ ( )
𝑚−1

This problem arose from a theorem of Ramsey. An infinite graph has an infinite point set and no
loops or multiple lines. Ramsey proved that every infinite graph contains mutually adjacent points.

Page 31
All known Ramsey numbers are given in Table, in accordance with the review article by Graver
and Yakel.

RAMSEY NUMBERS:

n/m 2 3 4 5 6 7
2 2 3 4 5 6 7
3 3 6 9 14 18 23
4 4 9 18

3.3 EXTREMAL GRAPHS

The following famous theorem of Turan is the forerunner of the field of extremal graph theory. As
usual, let [r] be the greatest integer not exceeding the real number r. and {r}= - [- r] the smallest
integer not less than r.

Theorem 3.3.1: The maximum number of lines among all p point graphs with no triangles is
[𝑝2 /4].

Proof. The statement is obvious for small values of p. An inductive proof may be given separately
for odd p and for even p; we present only the latter. Suppose the statement is true for all even 𝑝 ≤
2𝑛. We then prove it for p = 2n + 2. Thus, let G be a graph with p = 2n + 2 points and no triangles.
Since G is not totally disconnected, there are adjacent points u and v. The subgraph G' = G - {u, v}
has 2n points and no triangles, so that by the inductive hypotheses G' has at most [4𝑛2 /4] =𝑛2 lines.
How many mu lines can G have? There can be no point w such that u and v are both adjacent to w,
for then u, v and w would be points of a triangle in G. Thus if u is adjacent to k points of 𝐺′, v can
be adjacent to at most 2n-k points. Then G has at most

𝑛2 + k + (2n − k) + 1 = 𝑛2 + 2n + 1 = 𝑝2 / 4 = [𝑝2 / 4] lines.

To complete the proof, we must show that for all even p, there exists a (p, 𝑝2 / 4 ) graph with no
triangles. Such a graph is formed as follows: Take two sets 𝑉1 and 𝑉2 of p/2 points each and join
each point of 𝑉1with each point of 𝑉2 .

A bigraph (or bipartite graph*) G is a graph whose point set V can be partitioned into two subsets
𝑉1and 𝑉2 such that every line of G joins 𝑉1with 𝑉2 . For example, the graph of Fig. 3.3.1(a) can be
redrawn in the form of Fig. 3.3.1(b) to display the fact that it is a bigraph.

Page 32
 If G contains every line joining 𝑉1 and 𝑉2 then G is a complete bigraph. If 𝑉1 𝑎𝑛𝑑 𝑉2 have m and n
points, we write 𝐺 = 𝐾𝑚,𝑛 = 𝐾(𝑚, 𝑛). A star is a complete bigraph 𝐾1,𝑛 .

(a) (b)

Fig.3.3.1. A bigraph

Clearly 𝐾𝑚,𝑛 has mn lines. Thus, if p is even. K(p/2, p/2) has 𝑝2 /4 lines, while if p is odd, K( [p/2]
,{p / 2}) has [p / 2]{p/2} = [𝑝2 /4] lines . That all such graphs have no triangles follows from a
theorem of Konig.

Theorem 3.3.2: A graph is bipartite if and only if all its cycles are even.

Proof. If G is a bigraph, then its point set V can be partitioned into two set 𝑉1 and 𝑉2 so that every
line of G joins a point of 𝑉1with a point of 𝑉2 . Thus every cycle 𝑣1 𝑣2 . . . 𝑣𝑛 𝑣1 in G necessarily has
its oddly subscripted point in 𝑉1 , say, and the other in 𝑉2 , so that its length n is even.

For the converse, we assume, without loss of generality, that G is connected (for otherwise we can
consider the components of G separately). Take any point 𝑣1 ∈ 𝑉and let 𝑉1 consist of 𝑣1 and all
points at even distance from 𝑣1 while 𝑉2 = 𝑉 − 𝑉1 . Since all the cycles of G are even, every line of
G joins a point of 𝑉1 with a point of 𝑉2 . For suppose there is a line 𝑢𝑣 joining two points of 𝑉1 .Then
the union of geodesics from 𝑣1 to v and from 𝑉1to u together with the line uv contains an odd cycle,
a contradiction.

Theorem3.3.1 is the first instance of a problem in "extremal graph theory." for a given graph H.
find ex (p, H), the maximum number of lines that graph with p points can have without containing

Page 33
the forbidden subgraph Thus Theorem 2.3 states that ex (𝑝, 𝑘3 )= [𝑝2 / 4]. Some other results [E3]
in extremal graph theory are:

𝑒𝑥(𝑝, 𝐶𝑝 ) = 1 + (𝑝 − 1)(𝑝 − 2)/2,

𝑒𝑥(𝑝, 𝐾4 − 𝑥) = [𝑝2 /4],

𝑒𝑥(𝑝, 𝐾1,3 + 𝑥) = [𝑝2 /4].

Turán generalized his Theorem3.3.1 by determining the value 𝑒𝑥(𝑝, 𝐾𝑛 ) for all 𝑛 ≤ 𝑝,

(𝑛−2)(𝑝2 −𝑟 2 ) 𝑟
𝑒𝑥(𝑝, 𝐾𝑛 ) = + ( ),
2(𝑛−1) 2

where 𝑝 ≡ 𝑟 𝑚𝑜𝑑(𝑛 − 1) and 0≤ 𝑟 < 𝑛 − 1

A new proof of this result was given by Motzkin and Straus. It is also known that every (2𝑛, 𝑛2 + 1)
graph contains n triangles, every (𝑝, 3𝑝 − 5) graph contains two disjoint cycles for 𝑝 ≥ 6, and
every (3𝑛, 3𝑛2 + 1) graph contains 𝑛2 cycles of length 4.

3.4. INTERSECTION GRAPHS

Let S be a set and 𝐹 = { 𝑆1 , . . . . , 𝑆𝑝 } a nonempty family of distinct nonempty subsets of S whose

union is S. The intersection graph of F is denoted Ω(𝐹) and defined by 𝑉(Ω(𝐹)) = 𝐹 with 𝑆𝑖 and
𝑆𝑗 adjacent whenever 𝑖 ≠ 𝑗 𝑆𝑖 ∩ 𝑆𝑗 ≠ ∅. Then a graph G is an intersection graph on S if there
exists a family F subsets of S for which G ≅ Ω(F).

Theorem 3.4.1 Every graph is an intersection graph.

Proof. For each point 𝑉𝑖 of G , let 𝑆𝑖 be the union of {𝑉𝑖 } with the set of lines incident with 𝑉𝑖. Then
it is immediate that G is isomorphic with Ω (F) where 𝐹 = {𝑆𝑖 }.

In view of this theorem, we can meaningfully define another invariant. The intersection number 𝜔
(𝐺) of a given graph G is the minimum number of elements in a set S such that G is an intersection
graph on S.

Corollary 3.4.1 (a) 𝐼𝑓 𝐺 𝑖𝑠 𝑐𝑜𝑛𝑛𝑒𝑐𝑡𝑒𝑑 𝑎𝑛𝑑 𝑝 ≥ 3 𝑡ℎ𝑒𝑛 𝜔 (𝐺) ≤ 𝑞.

Proof. In this case, the points can be omitted from the sets 𝑆𝑖 used in the proof of the theorem, so
that 𝑆 = 𝑋(𝐺)
Corollary 3.4.1 (b) If G has 𝑃0 isolated points and no 𝐾2 components, then 𝜔(G) ≤ q + 𝑃0 .
The next result tells when the upper bound in Corollary 2.5(a) is attained.

Page 34
Theorem 3.4.2 Let G be a connected graph with 𝑝 > 3 points. Then 𝜔(G) = q if and only if G
has no triangles.
Proof. We first prove the sufficiency. In view of Corollary 2.5(a), it is only necessary to show that
o 𝜔(G) ≥ q q for any connected G with at least 4 points having no triangles. By definition of the
intersection number, G is isomorphic with an intersection graph Ω (𝐹) on a set S with |𝑆|=𝜔 (G).
For each point 𝑉𝑖 of G, let 𝑆𝑖 be the corresponding set. Because G has no triangles, no element of
S can belong to more than two of the sets 𝑆𝑖 and 𝑆𝑖 ∩ 𝑆𝑗 ≠ ∅ if and only if hat 𝑉𝑖 𝑉𝑗 is a line of G.
Thus we can form a 1-1 correspondenc between the of G and those elements of S which belong to
exactly two sets 𝑆𝑖 . Therefore 𝜔(G) ≤ |𝑆| ≥ 𝑞 so that 𝜔(G) = 𝑞.
To prove the necessity, let 𝜔(G) = 𝑞 and assume that G has a triang Then let 𝐺1 be a maximal
triangle-free spanning subgraph of G. By the preceding paragraph, 𝜔(𝐺1 ) = 𝑞1 = |𝑋(𝐺1 )|.
Suppose that 𝐺1 = Ω (F).

Where, F is a family of subsets of some set S with cardinality 𝑞1 .Let x be a line of G not in 𝐺1 and
consider𝐺2 = 𝐺1 + 𝑥 .Since𝐺1 is maximal triangle-free , 𝐺2 must have some triangle,say
𝑈1 𝑈2 𝑈3, where x =𝑈1 𝑈3. Denote by 𝑆1 𝑆2 𝑆3, the subsets of S corresponding to 𝑈1 , 𝑈2 , 𝑈3, .Now if 𝑈2
is adjacent is only 𝑈1 𝑎𝑛𝑑 𝑈3 𝑖𝑛 𝐺1 ,replace 𝑆2 by a singleton chosen from𝑆1 ∩ 𝑆2 ,and add that
element to 𝑆3 . Otherwise, replace 𝑆3, by the union of 𝑆3, and any elements in 𝑆1 ∩ 𝑆2 . In either case
this gives a family F’ of distinct subsets of S such that 𝐺2 = Ω(F’). Thus 𝜔(𝐺2 ) ≤ 𝑞1 while |X(𝐺2 )|
=𝑞1 + 1. If 𝐺2 ≅ 𝐺 then let (|X(G)| − |X(𝐺2 )| = 𝑞0

It follows that G is an intersection on a set with 𝑞1 + 𝑞0 elements. However, 𝑞1 + 𝑞0 = 𝑞 − 1

Thus , 𝜔 (G) < q ,completing the proof.
The intersection number of a graph had previously been studied by Erdos, Goodman,and posa.
They obtained the best possible upper bound for the intersection number of a graph with a given
number of points.

Theorem 3.4.3 For any graph G with 𝑝 ≥ 4 points, 𝜔 (G)≤ [𝑝2 /4].

Their proof is essentially the same that of Theorem3.3.1.

There is an intersection graph associated with every graph which depends on its complete
subgraphs. A clique of a graph is a maximal complete subgraph. The clique graph of a given graph
G is the intersection graph of G the family of cliques of G. For example, the graph G of Fig. 3.4
obviously has 𝑘4 as its clique graph. However, it is not true that every graph is the lique graph of

Page 35
some graph, for Hamelink has shown that the same graph G is a counterexample! F. Roberts and J.
Spencer have just charcterized clique graphs:

Theorem 3.4.4 A graph G is a clique graph if and only if it contains a family of complete subgraphs,
whose union is G, such that whenever every pai such complete graphs in some subfamily F' have a
nonempty inter Lion, the intersection of all the members of F' is not empty.

Figure.3.4.1 A graph and its clique graph

3.5. Excursion

A special class of intersection graphs was discovered in the field of genetics by Benzer when he
suggested that a string of genes representing a

bacterial chromosome be regarded as a closed interval on the real line. Hajós independently
proposed that a graph can be associated with every finite family F of intervals 𝑆𝑖 , which in terms of
intersection graphs, is precisely Ω (F). By an interval graph is meant one which is isomorphic to
some graph Ω (F), where F is a family of intervals. Interval graphs have been characterized by
Boland and Lekkerkerker and by Gilmore and Hoffman.

Fig.3.5.1 The union and join of two graphs

Page 36
3.6 Summary: Ramsey's theorem, in one of its graph-theoretic forms, states that one will find
monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph.
To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive
integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every
blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices
or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)

3.7 Keywords: The Problem of Ramsey, Extremal Graphs, Intersection Graphs, Excursion

3.8 Exercises:
1. Find the maximum number of lines in a graph with p points and no even cycles.
2. Find the extremal graphs which do not contain K4.
3. Every (𝑝, 𝑝 + 4) graph contains two line-disjoint cycles.
𝑝 𝑝
4. The only (𝑝, [𝑝2 /4]) graph with no triangles is 𝐾 ([2] . {2}).
𝑝 𝑝
5. Prove or disprove: The only graph on p points with maximum intersection number is 𝐾 ([2] , {2 }).

3.9 Reference

1. F. Harary, Graph Theory, Addison-Wesley, 1969.

2. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science, PHI,
2011.

3. B. Sooryanarayana and G. K. Ranganath, Text book of graph theory, S. Chand and Co. New
Delhi.

4. D.B. West, Introduction to Graph theory, Prentice Hall India 2001.

5. G. Chartrand and L. Lisniak, Graphs and Digraphs, Wordsworth, Inc. Belmont,

California, 1986.

Page 37
 UNIT – 4

OPERATIONS ON GRAPHS

Structure:

4.0. Objectives

4.1. Introduction

4.2. Union, Intersection and Ring sum

4.3. Deletion and Addition of Vertices/Edges

4.4. Decomposition

4.5. Complement of graph

4.6. Products of Graphs

4.7. Summary

4.8. Keywords

4.9. Exercises

4.10. References

Page 38
 4.0. Objectives
The objective of this unit is to make the learners conversant on different graph operations, mainly
 Union, Intersection, Ring sum, Deletion and Decomposition
 Compliments and Self complimentary graphs
 Cartesian product of graphs and Hypercube

4.1. Introduction
As is the case with most mathematical entities, it is convenient to consider a large graph as a
combination of small ones and to derive its properties from those of the small ones. Since graphs are
defined in terms of the sets of vertices and edges, it is natural to employ the set-theoretical terminology
to define operations between graphs. In particular: union, intersection, deletion and compliments and
decompositions play very important rule in further study of graph theory. Often at the end of the unit
we define Cartesian of graphs and Hypercube which are very advantageous in the study of computer
networks and parallel processing.

4.2. Union, Intersection and Ring sum

Union: Let G1 = (V1, E1) & G2 = (V2, E2) be any two graphs The union of graphs G1 and G2 is denoted
by G1  G2 is the graph whose vertex set is V1  V2 and the edge set is E1  E2. i.e. G1  G2
= (V1V2, E1E2) is called the union of graphs G1 & G2

Example:

G1:
v2
v1 v1v1v1 v2 G1  G2: v1 v2
G2: v3
v3
v5 v4 v4
v5 v4

Intersection:
The intersection of graphs G1 and G2, is denoted by G1 ∩ G2 is the graph whose vertex set is
V1∩V2 and the edge set is E1∩E2, provided V1∩V2 ≠  i.e. G1∩ G2 = (V1∩V2, E1∩E2), if V1∩V2 ≠ 

Example: For the above example,

G1 ∩ G2:
v2 v4
Ring sum: The ring sum of G1 & G2 denoted by G1ΔG2 (or G1  G2 ), is the graph whose vertex set is

Page 39
V1V2 & the edge set is E1ΔE2, where E1ΔE2 is the symmetric difference of E1 & E2

i.e. G1ΔG2 = (V1V2, E1ΔE2) is called the ring sum of G1 and G2, where E1ΔE2 is the symmetric
difference of E1 & E2 (The symmetric difference of E1 & E2 denotes the set of all those elements which
are in E1 or E2 but not in both, i.e. E1ΔE2 = (E1E2) – (E1∩E2).

Example: For the above example (Consider G1 and G2 which is given for Union of graphs)

v1 v2

G1 ∆ G2:
v3

v5 v4

4.3. Deletion and Addition of Vertices/Edges

If v is any vertex in G, then G – v denotes the subgraphs of G got by deleting vertex v and all edges
incident on v from G. The subgraph G – v is called as vertex-deleted subgraph of G.

If e is an edge of a graph G, then G – e denotes the subgraphs of G obtained by deleting edge e (but
not the end vertices) from G. The subgraph G – e is called as edge-deleted subgraph of G.

On the other hand, if vi and vj are not adjacent in G, the addition of edge vivj results in the smallest
supergraph of G containing the edge vivj. These operations are illustrated in the Figure 4.3.1.

Figure 4.3.1
Page 40
Note:
¤ Deletion of a vertex always results in the deletion of all edges incident on that vertex

¤ G – v is a induced subgraph of G induced by V1=V – {v}

¤ The deletion of an edge does not change the number of vertices, hence an edge-deleted subgraph
of a graph is a spanning subgraph of the graph.

¤ In general, if S is any set of edges in a graph G and W is any set of vertices in G then the subgraph
of G obtained by deleting S from G is denoted by G – S and the subgraph of G obtained by
deleting W and all the edges incident on vertices of W from G is denoted by G – W. [The
removal of a set of vertices or edges from G is defined by the removal of single
elements in succession.]

There are certain graphs for which the result of deleting a vertex or edge, or adding a edge, is
independent of the particular vertex or edge selected. If this is so for a graph G, we denote the result
accordingly by G – v, G – x, or G + x. [See Figure 4.3.2.]

Figure 4.3.2

Page 41
 Ulam's Conjecture* Let G and H be any two (p, q) graphs with p > 3 and v1, v2, , ,vp as vertices of

G, u1, u2 , up as vertices of H. If for each i, the subgraphs Gi  G  vi and Hi  H  ui are

isomorphic, then the graphs G and H are isomorphic.

There is an alternative point of view to this conjecture. Draw each of the p unlabeled graphs

G  vi on a 3×5 card. The conjecture then states that any graph from which these subgraphs can be
obtained by deleting one point at a time is isomorphic to G. Thus Ulam's conjecture asserts that any two
graphs with the same deck of cards are isomorphic.

4.4. Decomposition:

A graph G is said to be decomposed (or partitioned) into two subgraphs G1 & G2 if G1G2 = G, and
G1∩G2 = null graph

Example: In the following example G1 & G2 form decomposition of graph G.

v1 v1 v1 v2
v2
G2: v3
G: G1:
v3
v3
v5 v4 v4
v5 v4

4.5. Complement of a subgraph

Let G be a graph & G1 a subgraph of G, then the complement of G1 in G denoted by G – G1 (or G1 ) is

the subgraph of G obtained by deleting all the edges from G that belong to G1. In other words, if
G1= (V1, E1) is the subgraph of G = (V, E), then G1  G  E1.

Note: Also we have G1  GG1

G v3 G
K4

Page 42
Complement of a simple graph: Every simple graph of order n is a subgraph of the complete graph Kn.
Thus if G is a simple graph of order n, then, the complement of G in Kn. denoted by G is called the
complement of G.

Thus the complement G of simple graph G with n vertices is that graph which is obtained by deleting

those edges of Kn which belong to G. Thus, G  Kn  G  KnG

Note:
¤ G is the subgraph of Kn consisting of the n vertices in G and all edges that are not in G.
¤ If G = Kn, then G is null graph consisting of n vertices.
¤ Kn, G & G have the same vertex set, and the two vertices are adjacent in G if and only if they
are not adjacent in G

¤ Complement of G is G, i.e. G  G

Example:

K3 G G

K4 G G

Self-Complementary Graphs: A simple graph G which is isomorphic to its complement G is

called a self-complementary graph.

Example: Self-complementary Graph with 4 vertices

G G

¤ Two simple graphs G1 & G2 are isomorphic if and only if their complements ̅̅̅̅
𝐺1 and ̅̅̅̅
𝐺2 are
isomorphic.

Page 43
 Problem: If a simple graph G of order n is self-complementary, then show that either n or n – 1
must be a multiple of 4

Solution: If a simple graph G of order n is self-complementary, then G  G . Therefore, G and G

both have same number of edges. The total number of edges in G and G taken together must be
equal to number of edges in Kn. Since Kn has n (n – 1)/2 edges, it follows that each of G and G has
n (n – 1)/4 edges. Thus n (n – 1)/4 must be a positive integer, as such, either n or n – 1 must be a
multiple of 4.

4.6. Products of Graphs

A) Cartesian Product of Graphs: The Cartesian product of two graphs G1 and G2 is denoted by
G1  G2 , is a graph G such that V G  V (G1) V (G2 ) and two vertices (u1, v1) and (u2, v2 ) are

adjacent in G if and only if either u1  u2 and v1v2  E(G2 ) or v1  v2 and u1u2  E(G1 ) .

Example:
(a, x) (b, x) (c, x) (c, x)
G1:
a b c d
G1  G2 : (a, y) (b, y) (c, y) (c, y)

G2:
x y z
(a, z) (b, z) (c, z) (c, z)

Note:A convenient way of drawing G1  G2 is first to place a copy of G2 at each vertex of G1 (Figure

(b)) and then to join corresponding vertices of G2 in those copies of G2 placed at adjacent vertices of G1
(Figure (c)). Equivalently, G1  G2 can be constructed by placing a copy of G1 at each vertex of G2 and
adding the appropriate edges. It is very evident that G1 G2  G2 G1 .

Page 44
The n-cube Qn is one of the very important class of graphs recursively defined in terms of Cartesian
products. For n = 1 be Q1 is the graph K2. While for n ≥ 2, Qn is defined as Qn1  K2 . The graphs Q1, Q2
and Q3 are shown in the following figure.

The n-cube Qn can also be considered as that graph whose vertices are labeled, by the binary n-tuples (a1,
a2 ,…, an),where ai is 0 or 1 for 1  i  n and such that two vertices are adjacent if and only if their
corresponding n-tuples differ at precisely one coordinate. It is easily observed that Qn is an n-regular
graph of order 2n.

¤ The graphs Qn are often called Hypercube.

B) Composition Product of Graphs (or Lexicographic Product): The composition product of two
graphs G1 and G2, denoted by G1 [G2], is a graph G such that
(i) V (G) {(x, y): x V (G1), y V (G2)}
(ii) E(G) {{(a,b), (c, d)}: either ac  E(G1) or [a  c and bd  E(G2)]}
Note: Lexicographic product of two graphs is not commutative.

Page 45
Example: The graphs G1 and G2 and their composition product are shown in the figure below.

C) Normal Product of Graphs (or Strong Product): The normal product of two graphs G1 and G2,
denoted by G1 ° G2, is a graph G such that
(i) V (G) {(x, y): x V (G1), y V (G2 )}
(ii) E(G) {{(a,b), (c, d)}:[ a  c and bd  E(G2)] or [b  d and ac  E(G1)] or [ac  E(G1) and bd E(G2)]}

Note: Normal product of two graphs is commutative. Is it associative?

Example: The graphs G1 and G2 and their normal product are shown in the figure below.

D) Tensor Product of Graphs (or Kronecker Product): The Tensor product of two graphs G1 and
G2, denoted by G1 ⊗ G2, is a graph G such that
(i) V (G) {(x, y): x V (G1), y V (G2)}

(ii) E(G) {{(a,b), (c, d)}: ac  E(G1) and bd  E(G2 )}

Note: Tensor product of two graphs is commutative. Is it associative?

Page 46
 Note: G1° G2 = (G1×G2)  (G1 ⊗ G2) [observe this result with suitable examples]

4.7. Summary

Since graphs are defined in terms of the sets of vertices and edges, it is natural to employ the set-
theoretical terminology to define operations between graphs. In particular: Union, Intersection, Ring
sum and different products of graphs.

4.8. Key words

Union, Intersection, Compliment of a graph, Self-complimentary graphs, Cartesian product of graphs.

4.9. Exercises

1. Prove that Cn is self-complementary if and only if n = 5.

2. Let G be a simple graph of order n. If size of G is 56 and size of G is 80, then what is order of G?

3. Prove that two simple graphs G1 & G2 are isomorphic if and only if their complements
are isomorphic.

4. Define hypercube Qn of dimension ‘n’. Prove that Qn has n2n1 edges.

a) What is the dimension of hypercube with 524288 edges?

b) How many vertices are there in a hypercube with 4980736 edges?

5. Find Cartesian product, Composition product, Normal product and Tensor product of P3 and C4.

6. Find the number of edges the following graphs

i) C4 ×P4 ii) C4 [P4] iii) C4 ° P4 iv) C4 ⊗ P4

Page 47
4.10 References:

1. F. Harary, Graph Theory, Addison-Wesley, 1969

2. Narsingh Deo, Graph Theory with Applications to Engineering and Computer
Science, PHI, 2011.
3. B. Sooryanarayana and G. K. Ranganath, Text book of graph theory, S. Chand and
Co. New Delhi.
4. D.B. West, Introduction to Graph theory, Prentice Hall India 2001
5. G. Chartrand and L. Lisniak, Graphs and Digraphs, Wordsworth, Inc. Belmont,
California, 1986.

Page 48
 BLOCK – II
BLOCKS AND TREES

Page 49
 UNIT – 5
CUT VERTICES, BRIDGES AND BLOCKS

Structure:

5.0. Objectives

5.1. Introduction

5.2. Cut-sets

5.3. Cut-Vertices, Bridges and Blocks

5.4. Block Graphs and Cut-vertex graphs

5.5. Summary

5.6. Keywords

5.7. Exercises

5.8. References

Page 50
 5.0. Objectives
The objective of this unit is to make the learners conversant on –
 Cut-vertices, Bridges, Blocks and their characterizations
 Block Graphs and Cut-vertex graphs

5.1. Introduction
Although being connected is the most basic structural property that a graph may possess, more
information about its structure is provided by special vertices, edges and subgraphs it contains and
the symmetry it possesses. This is the theme of the current unit. The connectivity of graphs is a
particularly intuitive area of graph theory and extends the concepts of cut-vertex (cut-point), bridge,
and block. Two invariants called connectivity and line-connectivity are useful in deciding which of two
graphs is "more connected."

Some graphs are connected so slightly that they can be disconnected by the removal of a single vertex
or single edge. Such vertices and edges play a special role in graph theory, and we discuss these next.
In the beginning of the unit we discuss about cut-set and its properties, then we proceed to
characterizations of cut-vertex and bridges.

5.2. Cut-sets
In a connected graph G, a cut-set is a set of edges whose removal from G, leaves G disconnected (or
increase the number of components of G) provided removal of no proper subset of these edges
disconnects G. (Some authors define; the set of edges whose removal increase number of components

of the graph G, as cut-set and a cut-set is called minimal cut-set if of no proper subset of these edges
is a cut-set of G).

Examples:
G:

Figure: 5.2.1

Page 51
The set of edges {a, c, d, f} is a cut-set. There are many other cut-sets, such as {a, b, g}, {a, b, e, f},
{d, h, f} and {k}. The set of edges {a, c, h, d} is not a cut-set, because one of its proper subsets {a, c,
h} is a cut-set.

Theorem 5.2.1: Every cut-set in a connected graph G must contain at least one branch of every
spanning tree of G.

Proof: Let G be a connected graph, let Q be a minimal set of edges containing at least one branch of
every spanning tree of G. Consider G - Q the subgraph that remains after removing the edges in Q from
G. Since the subgraph G - Q contains no spanning tree of G, G - Q is disconnected (one component of
which may just consist of an isolated vertex). Also, since Q is a minimal set of edges with this property,
any edge e from Q returned to G - Q will create at least one spanning tree. Thus the subgraph G – Q +
e will be a connected graph. Therefore, Q is a minimal set of edges whose removal from G disconnects
G. This by definition is a cut-set.

Theorem 5.2.2: Every circuit has an even number of edges in common with any cut-set.

Proof: Consider a cut-set S in graph G. Let the removal of S partition the vertices of G into two
(mutually exclusive or disjoint) subsets V1 and V2. Consider a circuit Γ in G. If all the vertices in Γ are
entirely within vertex set V1 (or V2), the number of edges common to S and Γ is zero, that is, N(S
∩T) = 0, an even number.

If, on the other hand, some vertices in Γ are in V1 and some in V2, we traverse back and forth between
the sets V1 and V2 as we traverse the circuit. Because of the closed nature of a circuit, the number of
edges we traverse between V1 and V2 must be even. And since very edge in S has one end in V1 and the
other in V2 and no other edge in G has this property (of separating sets V1 and V2), the number of edges
common to S and Γ is even.

Theorem 5.2.3: The ring sum of any two cut-sets in a graph is either a third cut-set or an edge
disjoint union of cut-sets.

Proof: Let S1 and S2 be two cut-sets in a given connected graph G. Let V1 and V2 be the (unique and
disjoint) partitioning of the vertex set V of G corresponding to S1. Let V3 and V4 be the partitioning
corresponding to S2. Clearly

V1 𝖴 V2 = V and V1 ∩ V2 = ∅,

V3 𝖴 V4 = V and V3 ∩ V4 = ∅,

Page 52
Now let the subset (V1 ∩ V4) 𝖴 (V2 ∩ V3) be called V5 and this by definition is the same as the ring sum
of V1 and V3. Similarly let the subset (V1 ∩ V3) 𝖴 (V2 ∩ V4) be called V6, which is the same as ring sum
of V2 and V3.

The ring sum of the two cut-sets of S1 and S2 can be seen to consist only of edges that join vertices in
V5 to those in V6. Also there are no edges outside the ring sum of S1 and S2 that join vertices in V5 to
those in V6.

Thus the set of edges in ring sum of S1 and S2 produces a partitioning of V into V5 and V6 such that
V5 𝖴 V6 = V and V5 ∩ V6 = ∅,

Hence the ring sum of S1 and S2 is a cut-set if the subgraphs containing V5 and V6 each remain connected
after the ring sum of S1 and S2 is removed from G. Otherwise, ring sum of S1 and S2 is an edge-disjoint
union of cut-sets.

5.3. Cut-Vertices, Bridges and Blocks

A cut-vertex (or cut-point) of a graph is vertex whose removal increases the number of components,
and a bridge is an edge of a graph, whose removal increases the number of components. Thus if v is a
cut-vertex of a connected graph G, then G – v is disconnected. A nonseparable graph is connected,
nontrivial, and has no cut-vertices. A block of a graph is a maximal nonseparable subgraph. If G is
nonseparable, then G itself is often called a block.

For the graph G represented in the Figure 5.3.1, u, v and w are cut-vertices, x and y are bridges. B1, B2,
B3, B4 and B5 are the blocks of G. Each edge of a graph lies in exactly one of its blocks, as does each
vertex which is not isolated or a cut-vertex. Furthermore, the edges of any cycle of G also lie entirely
in a single block. Thus in particular, the blocks of a graph partition its edges and its cycles regarded
as sets of edges. The theorems of this unit present several equivalent conditions for each of
these concepts. The following theorem gives a characterization of cut-vertices

y
u
v w
G:
x

Page 53
 B4
B1 B2
B3 B5

Figure 5.3.1: A graph and its blocks

Theorem 5.3.1: A vertex v of a connected graph G is a cut-vertex of G if and only if there exist vertices
u and w (u, w ≠ v) such that v is on every u-w path of G.

Proof: Let v be a cut-vertex of G; so the graph G − v is disconnected. If u and w are vertices in different
components of G − v, then there are no u-w paths in G − v. However, since G is connected, there are
u-w paths in G. Therefore, every u-w path of G contains v.

Conversely, assume that there exist vertices u and w in G such that the vertex v lies on every u-w path
of G. Then there are no u-w paths in G − v, implying that G − v is disconnected and that v is a cut-
vertex of G.

Note: The complete graphs have no cut-vertices while, at the other extreme, each nontrivial path
contains only two vertices that are not cut-vertices. In order to see that this is the other extreme, we
prove the following theorem.

Theorem 5.3.2: Every nontrivial connected graph contains at least two vertices that are not cut-
vertices.

Proof: Let u and v be vertices of a connected non-trivial graph G such that d (u, v) = diam (G). We
prove none of u or v is a cut-vertex. Suppose at least one of u and v is a cut-vertex, we arrive a
contradiction. Without loss of generality, say v is a cut-vertex of G. Let w be a vertex belonging to a

component of G − v not containing u. Since very u-w path in G contains v, and every u-w path in G
contains v, we conclude that d (u, w) > d (u, v) = diam (G), which is a contradiction. Hence the desired
result now follows.
The following theorem is more generalised form of the Theorem 5.3.1.

Page 54
Theorem 5.3.3: Let v be a vertex of a connected graph G. The following statements are equivalent:

A. v is a cut-vertex of G.
B. There exist vertices u and w distinct from v such that v is on every u-w path.
C. There exists a partition of the set of vertices V− {v} into subsets U and W such that for any
vertices u U and w W, the vertex v is on every u-w path.

Proof: (A) implies (C) Since v is a cut-vertex of G, G − v is disconnected and has at least two
components. Form a partition of V − {v} by letting U consist of the vertices of one of these components
and W the vertices of the others. Then any two vertices u  U and w  W lie in different components
of G − v. Therefore, every u-w path in G contains v.

(C) implies (B) This is immediate since (B) is a special case of (C).

(B) implies (A) If v is on every path in G joining u and w, then there cannot be a path joining these
vertices in G – v is disconnected, so v is a cut-vertex of G.

Let G be a graph and e = xy be a bridge in G. If deg (x) and deg (y) >1, then x and y are cut verticesof
G. That is an end-vertex of a bridge is a cut vertex provided it is not a pendent vertex.

¤ The complete graph K2 is the only connected graph containing a bridge but no cut-vertices.

Bridges are characterized in a manner similar to that of cut-vertices; the proofs too are similar to thatof
Theorem 5.3.1 and Theorem 5.3.3. Hence the proofs of the following theorems left to the reader.

Theorem 5.3.4: An edge e of a connected graph G is a bridge of G if and only if there exist vertices
u and w such that e is on every u-w path of G.

Theorem 5.3.5: Let x be an edge of a connected graph G. The following statements are equivalent:

A. x is a bridge of G.
B. x is not on any cycle of G.
C. There exist vertices u and v of G such that the edge x is on every path joining u and v.
D. There exists a partition of V into subsets U and W such that for any vertices u  U and w  W,
the edge x is on every path joining u and w.

Page 55
Theorem 5.3.6: Let G be a connected graph with at least three vertices. The following statements are
equivalent:
A. G is a block.
B. Every two vertices of G lie on a common cycle.
C. Every vertex and edge of G lies on a common cycle.
D. Every two edges of G lie on a common cycle.
E. Given two vertices and one edge of G, there is a path joining the vertices which contains the
edge.
F. For every three distinct vertices of G, there is a path joining any two of them which contains
the third.
G. For every three distinct vertices of G, there is a path joining any two of them which does not
contain the third.

Proof: (A) implies (B) Let u and v be distinct vertices of G, and let U be the set of vertices different
from u which lie on a cycle containing u. Since G has at least three vertices and no cut-vertices, it has
no bridges; therefore, every vertex adjacent to u is in U, so U is not empty.

P1 P

u P0 w
u w
w v v
P2 P2

(a) (b)
Figure.5.3.2 Paths in block

Suppose v is not in U. Let w be a vertex in U for which the distance d (w, v) is minimum. Let P0 be a
shortest w-v path, and let P1 and P2 be the two u-w paths of a cycle containing u and w (see Figure
5.3.2 (a)). Since w is not a cut-vertex, there is a u-v path P' not containing w (see Figure 5.3.2 (b)). Let
w' be the vertex nearest u in p1 which is also in P0, and let u' be the last vertex of the u-w' subpath of
P' in either Pl or P2. Without loss of generality, we assume u' is in Pl.

Let Q1 be the u-w' path consisting of the u-u' subpath of P1 and the u'-w' subpath of P1. Let Q2 be the
u-w' path consisting of P2 followed by the w-w1 subpath of Po. Then Q1 and Q2 are disjoint u-w' paths.
Together they form a cycle, so w' is in U. Since w' is on a shortest w-v path, d(w', v) < d(w, v). This
contradicts our choice of w, proving that u and v do lie on a cycle.

Page 56
(B) implies (C) Let u be a vertex and vw a edge of G. Let Z be a cycle containing u and v. A cycle Z'
containing u and vw can be formed as follows. If w is on Z, then Z' consists of vw together with the v-
w path of Z containing u. If w is not on Z, there is a w-u path P not containing v, since otherwise v
would be a cut-vertex by Theorem 5.3.1. Let u' be the first vertex of P in Z. Then Z' consists of vw
followed by the w-u' subpath of P and the u'-v path in Z containing u.

(C) implies (D) This proof is analogous to the preceding one, and the details are omitted.

(D) implies (E) Any two vertices of G are incident with one edge each, which lie on a cycle by (D).
Hence any two vertices of G lie on a cycle, and we have (B), so also (C). Let u and v be distinct vertices
and x a edge of G. By statement (C), there are cycles Zl containing u and x, and Z2 containingv and x.
lf v is on Z1 or u is on Z2, there is clearly a path joining u and v containing x. Thus, we need only
consider the case where v is not on Z1 and u is not on Z2. Begin with u and proceed along Z1 until
reaching the first vertex w of Z2, then take the path on Z2 joining w and v which contains x. This walk
constitutes a path joining u and v that contains x.

(E) implies (F) Let u, v, and w be distinct vertices of G, and let x be any edge incident with w. By (E),
there is a path joining u and v which contains x, and hence must contain w.

(F) implies (G) Let u, v, and w be distinct vertices of G. By statement (F), there is a u-w path P
containing v. The u-v subpath of P does not contain w.

(G) implies (A) By statement (G), for any two vertices u and v, no vertex lies on every u-v path. Hence,
G must be a block.

Theorem 5.3.7: Every nontrivial connected graph has at least two vertices which are not cut-vertices.

Proof: Let u and v be vertices at maximum distance in G, and assume v is a cut-vertex. Then there is
a vertex w in a different component of G – v than u. Hence v is in every path joining u and w, so
d (u, w) > d (u, v), which is impossible. Therefore, v and similarly u are not cut-vertices of G.

A graph G is a critical block if G is a block and for every vertex v, the graph G – v is not a block. Hence
a block G is noncritical if and only if there exists a vertex v of G such that G – v is also a block. There
is an analogous concept concerning edges. A graph G is a minimal block if G is a block and for every
edge e, the graph G – e is not a block. The block G1 of Figure 5.3.3, is minimal and noncritical, while
the block G2 is critical but not minimal.

Page 57
 G2 :

Figure 5.3.3: A graph and its blocks

5.4. Block Graphs and Cut-vertex Graphs

There are several intersection graphs derived from a graph G which reflect its structure. If we take
the blocks of G as the family F of sets, then the intersection graph Ω(F) is the block graph of G, denoted
by B(G). The blocks G correspond to the vertices of B(G) and two of these vertices are adjacent
whenever the corresponding blocks contain a common cut-vertex of G. On the other hand, to obtain a
graph whose vertices correspond to the cut-vertices of G, we can take the sets S to be the union of all
blocks which contain the cut-vertex vi. The resulting intersection graph Ω(F) is called the cut-vertex
graph, C(G). Thus two vertices of C(G) are adjacent if the cut-vertices of G to which they correspond
lie on a common block. Note that C(G) is defined only for graphs G which have at least one cut-vertex.
Figure 5.4.1 illustrates these concepts.

C(G):G: B(G):

Figure 5.4.1: A graph, its block graph, and its cut-vertex graph
Theorem 5.4.1 A graph H is the block graph of some graph if and only if every block of H is complete.

Proof: Let H = B(G), and assume there is a block Hi, of H which is not complete. Then there are two
vertices in Hi which are nonadjacent and lie on a common cycle Z of length at least 4. But the union
of the blocks of G corresponding to the vertices of Hi which lie on Z is then connected and has no

Page 58
cut-vertex, so it is itself contained in a block, contradicting the maximality property of a block of a
graph.

On the other hand, let H be a given graph in which every block is complete. Form B(H), and then form
a new graph G by adding to each vertex Hi of B(H) a number of pendent edges equal to the number of
vertices of the block Hi which are not cut-vertices of H. Then it is easy to see that B(G) is isomorphic
of H.

¤ Clearly the same criterion also characterizes cut-vertex graphs.

5.5. Summery
A cut-vertex (or cut-point) of a graph is vertex whose removal increases the number of components,
and a bridge is an edge of a graph, whose removal increases the number of components. Thus if v is a
cut-vertex of a connected graph G, then G – v is disconnected. A nonseparable graph is connected,
nontrivial, and has no cut-vertices. A block of a graph is a maximal nonseparable subgraph. Throughout
the unit we study different characterizations bridge, blocks and cut-vertices.

We define two intersection graphs namely block graph and a cut-vertex graph. If we take the blocks of
G as the family F of sets, then the intersection graph Ω(F) is the block graph of G, denoted by B(G).
The blocks G correspond to the vertices of B(G) and two of these vertices are adjacent whenever the
corresponding blocks contain a common cut-vertex of G. On the other hand, to obtain agraph whose
vertices correspond to the cut-vertices of G, we can take the sets S to be the union of all blocks which
contain the cut-vertex vi. The resulting intersection graph Ω(F) is called the cut-vertex graph, C(G).

5.6. Keywords
Cut-vertex, Cut-point, Bridge, Block, Intersection Graph, Block Graph.

5.7. Exercises
1. What is the maximum number of cut-vertices in a graph with p vertices?

2. A cubic graph has a cut-vertex if and only if it has a bridge.

3. The smallest number of vertices in a cubic graph with a bridge is 10.

4. Prove that if v is a cut-vertex of a connected graph G, then v is not a cut-vertex of G.

5. Prove that an edge e of a connected graph G is a bridge of G if and only if there exist vertices
u and w such that e is on every u-w path of G.

Page 59
 6. Prove that an edge e of a graph G is a bridge of G if and only if e lies on no cycle of G.

7. Prove that a connected graph with at least two edges is a block if and only if any two adjacent
edges lie on a cycle.

8. Prove that a graph G of order at least 3 is nonseparable if and only if there exist two internally
disjoint u-v paths for every two distinct vertices u and v of G.

9. Let G be a connected graph with one or more cut-vertices. Then prove that among the blocks
of G, there are at least two which contain exactly one cut-vertex of G.

10. Prove that the center of every connected graph G lies in a single block of G.

11. If G is a critical block of order at least 4, then prove that G contains a vertex of degree 2.

12. If G is a minimal block of order at least 4, then prove that G contains a vertex of degree 2.

5.8. References

1. F. Harary, ‘Graph Theory’, Addison-Wesley, 1969

2. G. Chartrand and L. Lisniak, ‘Graphs and Digraphs’, Wordsworth, [Link], California,
1986.
3. Narsingh Deo, ‘Graph Theory with Applications to Engineering and Computer Science’, PHI,
2011.

Page 60
 UNIT – 6
TREES AND ITS PROPERTIES

Structure:

6.0. Objectives

6.1. Introduction

6.2. Definition and Basic Properties of Trees

6.3. Rooted Trees and applications

6.4. Spanning trees

6.5. Summary

6.6. Keywords

6.7. Exercises

6.8. References

Page 61
6.0. Objectives
The objective of this unit is to make the learners conversant on –
 Trees and Characterization of trees
 Rooted/Directed trees and applications in coding theory
 Spanning tree

6.1. Introduction
There is one simple and important kind of graph which has been given the same name by all authors,
namely a tree. The concept of a tree is probably the most important in graph theory, especially for those
interested in applications of graphs. Trees are important not only for sake of their applicationsto many
different fields, but also to graph theory itself. One reason for the latter is that the very simplicity of
trees makes it possible to investigate conjectures for graphs in general by first studying the situation
for trees. An example is provided by Ulam's conjecture mentioned in unit 4.
Several ways of defining a tree are developed. Using geometric terminology, we study centrality of
trees. This is followed by a discussion of a tree which is naturally associated with every connected
graph. Finally, we see how each spanning tree of a graph G gives rise to a collection of independent
cycles of G.

6.2. Definition and Basic Properties of Trees

A connected graph G which has no cycles is called Tree. A graph G which has no cycles is called an
acyclic graph. A forest is an acyclic graph (need not be connected if it is connected then it is a tree).

Thus every component of a forest is a tree. There are several observations that can be made regarding
trees.

Examples:

(a) (b) (c)

Page 62
In the above example the graphs represented by (a), (b) and (c) all are trees.
The following are examples for graphs which are not trees.

`
(a) (b) (c)

Note:

¤ A graph which is tree usually denoted by T.

¤ Pendent vertex of a tree is also called leaf or end vertex.

Basic properties of Trees

Theorem 6.2.1: In a tree there is one and only one path between every pair of vertices.

Proof: Let G be a tree. Then G is a connected simple graph. Since G 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 G, then the union of these two paths forms a cyclein
G. a contradiction to that G is a tree. (Tree has no cycles)

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

Theorem 6.2.2: In a graph G if there is one and only one path between every pair of vertices, then G
is a tree.

Proof: Let G be a graph such that there is one and only one path between every pair of vertices in G,
then we have to prove that G is a tree.

Since there is a path between every pair of vertices in G, it is obvious that G is connected. Since there
is only one path between every pair of vertices, G cannot have a cycle. (Because, if there is a cycle,
then there exist two paths between two vertices of the cycle.) Thus, G is a connected graph containing
no cycles. This means that G is a tree. This completes the proof.
Note: The above two theorems Theorem 6.2.1 and Theorem 6.2.2, together can be stated as follows“A
graph G is a tree if and only if there is one and only one path between every pair of vertices.”

Page 63
 Theorem 6.2.3: A tree with n vertices has n – 1 edges.

Proof: We prove the theorem by induction on n (the number of vertices).

The theorem is obvious for n = 1, n = 2 and n = 3; see the trees in following figure.

n=1 n=2 n =3

Assume that the theorem holds for all trees with n vertices where n < k, for a specified positive
integer k ≥ 2. Consider a tree T with k + 1 vertices.

Let e = {u, v} be an edge in T. Since T is a tree and in a tree there exist only one path between u and
v. Therefore, T – e is disconnected and consists of exactly two components, say T1 and T2.

Since T does not contain any cycle, the components T1 and T2 too do not contain any cycles. Hence,
T1 and T2 are trees.

Both of these trees have less than k + 1 vertices each. Therefore, by our assumption, the theorem holds
for these trees. That is, each of T1 and T2 contains number of edges one less than the number of vertices.
Since the total number of vertices in T1 and T2 (taken together) is k + 1, the total number of edges in
T1 and T2 (taken together) is (k + 1) – 2 = k–1. Thus, T–e contains (k–1) edges. (Because T1 and T2
taken together is T–e.) Consequently, T has exactly k edges.

Hence by induction the theorem is true for all positive integers n. Thus a tree with n vertices has n – 1
edges.

Theorem 6.2.4: A 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. Assume that G is not a tree.
Then G contains a cycle, say C. Let e be an edge in C. The graph G will not become disconnected if e
is deleted. Thus, G — e is a connected graph. But on the other hand, G — e has n vertices and n — 2
edges. Therefore, it cannot be connected. This is a contradiction to that “A connected graph with n
vertices has at least n – 1 edges”. Hence G must not have a cycle; this means that G must be a tree.
This completes the proof of the theorem.

Note: Theorems 6.2.3 and 6.2.4 can be put together in the following combined form:

“A graph with n vertices is a tree if and only if it is connected and has n — 1 edges”.

Page 64
Theorem 6.2.5: A connected graph G is a tree if and only if adding an edge between any two vertices
in G creates exactly one cycle in G.
Proof: Suppose a connected graph G is a tree. Then G has no cycles and there is exactly one path
between any two vertices u, v. If we add an edge between u and v then an additional path is created
between u and v and the two paths constitute a cycle. Since G had no cycles earlier, this is the only
cycle which G now possesses.
Conversely, suppose G is connected and adding an edge between any two vertices u and v in G creates
exactly one cycle in G. This implies that, before adding this edge, exactly one path was there between
u and v. This implies that G is a tree.
This completes the proof of the theorem.
Minimally Connected graph:
A connected graph is said to be minimally connected if the removal of any one edge from it
disconnects the graph.
Example: The graphs shown in following figures are minimally connected. As already noted all of
these graphs are trees as well.

(a) (b) (c)

Theorem 6.2.6: A connected graph is a tree if and only if it is minimally connected.

Proof: We prove the contra positive of the statement. Suppose G is a connected graph which is not a
tree. Then G contains a cycle C. The removal of any one edge e from this cycle will not make the graph
disconnected. Therefore, G is not minimally connected. Thus, if a connected graph is not a tree then it
is not minimally connected. This is equivalent to saying that if a connected graph is minimally
connected then it is a tree.

Conversely, suppose G is a connected graph which is not minimally connected. Then there exists an
edge e in G such that G – e is connected. Therefore, e must be in some cycle in G. This implies that
G is not a tree. Thus, if a connected graph is not minimally connected then it is not a tree. This is

equivalent to saying that if a connected graph is a tree, then it is minimally connected

(contrapositive). This completes the proof of the theorem.

Theorem 6.2.7: Every tree T has at least two pendent vertices (leaves).

Proof: The result is obvious. (Left as an exercise to the students.)

Page 65
 Theorem 6.2.8: A sequence 𝑑1 , 𝑑2 , 𝑑3 , … , 𝑑𝑛 (𝑛 ≥ 2) of positive integers is the degree sequence of
a tree of order n if and only ∑𝑛𝑖=1 𝑑𝑖 = 2𝑛 − 2.

Proof: First, let 𝑇 be a tree of order n and size m with degree sequence 𝑑1 , 𝑑2 , 𝑑3 , … , 𝑑𝑛 . Then,
∑𝑛𝑖=1 𝑑𝑖 = 2𝑚 = 2(𝑛 − 1) = 2𝑛 − 2.
We verify the converse by induction. For 𝑛 = 2, the only sequence of two positive integers with sum
equal to 2 is 1,1 and this is the degree sequence of the tree K2. Assume now that whenever a sequence
of n – 1 ≥ 2 positive integers has the sum 2(n – 2) = 2n – 4, then it is the degree sequence of a tree of
order n – 1.

Let 𝑑1 , 𝑑2 , 𝑑3 , … , 𝑑𝑛 . be a sequence of n positive integers with ∑𝑛𝑖=1 𝑑𝑖 = 2𝑛 − 2. We show that this

is degree sequence of a tree. Suppose that 𝑑1 ≥ 𝑑2 ≥ ⋯ ≥ 𝑑𝑛 . Since each term 𝑑𝑖 is a positive integer
and ∑𝑛𝑖=1 𝑑𝑖 = 2𝑛 − 2, it follows that2 ≤ 𝑑1 ≤ 𝑛 − 1 and 𝑑𝑛−1 = 𝑑𝑛 = 1.

Hence, 𝑑1 − 1, 𝑑2 , … 𝑑𝑛−1 is a sequence of 𝑛 − 1 positive integers whose sum is 2n – 4. By the

inductive hypothesis, then, there exists a tree T  of order 𝑛 − 1 with 𝑉(𝑉(𝑇 ′ ) = {𝑣1 , 𝑣2 , 𝑣3 , … , 𝑣𝑛−1 })
such that deg(v1)  d1 1 and deg(vi )  𝑑𝑖 fo 6.2.9. r 2 ≤ 𝑖 ≤ 𝑛 − 1. Let T be the tree obtained from

T  by adding a new vertex 𝑣𝑛 and joining it to 𝑣1 . The tree T then has the degree sequence
𝑑1 , 𝑑2 , 𝑑3 , … , 𝑑𝑛 . This completes the proof.

Theorem 6.2.9. Let T be a non-trivial tree with (T )  k, (k ≥2) and ni be the number of vertices of
degree i, for 𝑖 = 1,2, … , 𝑘. Then n1  n3  2n4  (k  2)nk  2.

Proof: First, let T be a tree of order n and size m.

Then, ∑𝑛𝑖=1 𝑛𝑖 = 𝑛 and ∑𝑛𝑖=1 𝑖𝑛𝑖 = 2𝑚 = 2(𝑛 − 1) = 2𝑛 − 2 = 2( ∑𝑛𝑖=1 𝑛𝑖 ) − 2.
This implies ∑𝑛𝑖=1(𝑖 − 2)𝑛𝑖 + 2 = 0 …………………………….(1)
Solving (1) for we get 𝑛1 we get 𝑛1 = 𝑛3 + 2𝑛4 + ⋯ + (𝑘 − 2)𝑛𝑘 + 2.
There are some classes of trees with which we should be familiar. Of course, the paths Pn and stars
𝐾1,𝑛 are trees. A tree T is a double star if it contains exactly two vertices that are not end-vertices
(leaves) necessarily, these vertices are adjacent. A caterpillar is a tree T with the property that the
removal of the end-vertices of T results in a path. This path is referred to as the spine of the caterpillar.
If the spine is trivial, the caterpillar is a star; if the spine is K2, then the caterpillar is a double star.
Examples of a double star and caterpillar are shown in Figure 6.2.4.

Knowledge of the properties of trees is often useful when attempting to prove certain results about
graphs in general. Because of the simplicity of the structure of trees, every graph ordinarily contains
a number of trees as subgraphs. Of course, every tree of order n or less is a subgraph of Kn. A more
general result is given next theorem.

Page 66
 Theorem 6.2.10: Let T be a tree order k, (k ≥1) and let G be a nontrivial graph with  (G)  k 1
Then T is a Subgraph of G.

Proof: We prove the result by induction k. The result is obvious for k = 1 and k = 2, since K1 and K2
are subgraphs of every nontrivial graph.

Assume for each tree T  of order k – 1, k ≥ 3 and every graph H with  (H )  k  2 has T  as a

subgraph. Let T be a tree order k and let G be a nontrivial graph with  (G)  k 1 . We show that T
is a subgraph of G.

Let v be an end vertex of T and let u be the vertex of T adjacent to v. The graph T – v is necessarily a
tree of order k – 1. The graph G has  (G)  k 1  k  2 ; thus by inductive hypothesis, T – v is a

subgraph of G. Let u denotes the vertex of G that corresponds to u. Since degG u  k 1 and T – v

has order k – 1, the vertex u is adjacent to a vertex w that corresponds to no vertex of w that corresponds
to no vertex of T – v. Therefore, T is a subgraph of G.

Now we introduce another revolutionary result by Ringel which attracted many young researchers of
20th century.

Ringel’s Conjecture: For every tree T of size m, the complete graph 𝐾2𝑚+1 is T-decomposable. [i.e.
𝐾2𝑚+1 can be decomposed into isomorphic trees of size m.]

For example, K9 can be decomposed into 9 subgraphs, all isomorphic to K1,3. The Ringel’s Conjecture
is still an open problem, one can take-up proving/disproving the conjecture as a challenge.

6.3. Rooted Trees and applications

Let D be a directed graph and G be its underlying graph. We say that D is directed tree if G is a
tree. A directed tree T is called rooted tree if

i) T contains unique vertex r called the root, whose in-degree is equal to 0 and

ii) The in-degree of all other vertices is equal to 1.

Note:

¤ A vertex v of rooted tree is said to be at kth level vertex or has level number k if the length ofthe

Page 67
 path from r to v is k.

¤ If T is a rooted tree and h is the largest level number achieved by a leaf of T, then T is said to have
height h.

If v1 and v2 are two vertices such that v1 has a lower level number than v2 and there is a path from v1
to v2 then we say that v1 is an ancestor of v2, or that v2 is a descendant of v1. In particular, if v1 and v2
are such that v1 has a lower level number than v2 and there is an edge (directed edge) from v1 to v2 then
v1 is called the parent of v2 or v2 is called the child of v1. Two vertices with a common parent are
referred to as siblings. A vertex whose out-degree is 0 is called a leaf. A vertex which is not a leaf is
called an internal vertex.

Example: r

v1 v2
T:
v5
v3 v4 v6

v7 v8

In the above example T is a rooted tree with r as a root. We observe the following.

1. The root vertex r is at level 0, v1 and v2 are at level 1, v3, v4, v5 and v6 are at level 2, the
vertices v7 and v8 are at level 3. The height of the tree is 3.

2. The vertex v2 is ancestor of the vertices v7, v8, v5 and v6 or v7, v8, v5 and v6 are descendent of
v2. The vertex v1 is not ancestor of v5.

3. v1 is parent of v3 and v4 or v3 and v4 children of v1.

4. v5 and v6 are siblings, but v4 and v5 are not siblings.

5. v7, v8, v3, v4 and v6 are leaves and the remaining vertices are internal vertices.
m-ary tree: A rooted tree T is called an m-ary tree if every vertex of T is of out-degree ≤ m; that is if
every vertex of T has at most m children. A rooted tree T is called a 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.

Examples: T2:
T1:

In the above example T1 is a 3-ary tree but not complete. T2 is a complete 3-ary tree.

Page 68
 Binary tree: An m-ary tree for with m = 2 is called a binary tree. In other words, a rooted tree T is
called a binary tree if every vertex of T is of out-degree ≤ 2; that is if every vertex has at most two
children.

A complete m-ary tree for which m = 2 is called a complete binary tree. In other words, a rooted tree
T is called a complete binary tree if every internal vertex of T is of out-degree 2; that is if every internal
vertex has exactly two children.

Balanced tree: If T is a rooted tree and h is the largest level number achieved by a leaf of T, then T is
said to have height h. A rooted tree of height h is said to be balanced if the level number of every leaf
is h or h – 1.

Full binary tree: 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.

T1: T3 :
T2 :

In the above example T1 is a binary tree, it is not a complete binary tree. T2 is a complete binary tree
also it a balanced binary tree. T3 is a full binary tree.

Now we discuss applications of rooted trees in binary prefix coding. Among the topics to which discrete
mathematics is applied, coding theory is one wherein different finite structures play a major role. These
enable us to represent and transmit information that is coded in terms of the symbols in a given
alphabet. For instance, the way we most often code, or represent, internally in a computer is by means
of strings of fixed length, using the symbol 0 and 1.

Binary Sequence: A sequence consisting only 0 and 1 is called a binary sequence.

Examples: 00110, 000, 11, 010101000000, etc

Prefix code: Let P be a set of binary sequence that represent a set of symbols. Then P is called prefix
code, if no sequence in P is a prefix code for any other sequence in P.

Examples: P1 = {0011, 000, 11, 0101, 10, 011} P2 = {01, 001, 000, 101, 110, 111}

Both P1 and P2 represent prefix code for some set of symbols. (We observe no sequence in P1 or P2 is
not prefix for any other sequence in P1 or P2 respectively.)

P3 = {001, 000, 11, 0101, 1110} P4 = {01, 001, 00, 101, 110, 111}

Page 69
 P3 is not prefix code for any set of symbols, because sequence 11 in P3 is prefix for the sequence 1110
in P3. Similarly, P4 is not prefix code for any set of symbols, because sequence 00 in P4 is prefix for
the sequence 001 in P4.

Note: For given set of prefix codes we can construct a (complete) binary tree representing the codes
and vice-versa. For the above example P1 and P2 can be represented by binary trees T1 and T2 as
follows.

T1: 1
0
T2: 1
1 0
0 1 0
0 1
0 1 0 1 10 0 1
11
1
1 0 01 0 1
001 011 1
000
0101
000 001 101 110 111

The codes we developed in this section, however, will use strings of different lengths. However, in
English (or any other) language, not all letters occur with the same frequency. Consequently, it would
be more efficient to use binary sequence of different lengths, with most frequently occurring letters
(such as a. e. i, s, t) represented by shortest possible sequences.

Weighted Tree: Consider the set of n positive integer w1, w2, . . ., wn. The binary tree whose n leaves
are assigned these n integers in one to one manner is called a weighted tree, where w1, w2, . . ., wn are
n
called weights. The weight of the tree is denoted by W(T) and defined by W T   wi l (wi ) where l
i1
(wi) is level number of leaf assigned wi.

Optimal Tree: For given set of weights, the weighted tree having least weight is called optimal tree.

In the following figure T1 and T2 shows two complete binary trees for the weights 3, 5, 6 and 9.
Whereas we observe W (T1)  (3  9  5  6)  2  46 and W (T2 )  33  53  6 2  91  45 . More

over T2 is an optimal tree for the given set of weights 3, 5, 6 and 9. (Verify!)

Page 70
 T2

T1:

The construction of optimal tree is competently explained by Huffman. We leave Huffman’s

construction of optimal tree and prix codes generated by it as an exercise to the students.

6.4. Spanning Tree

The second part of the chapter introduces the spanning tree—another important notion in the theory
of graphs. The relationships among circuits, trees, and so on, in a graph are explored. As remarked
above, the growth of graph theory has been due in large measure to its essential role in the applied
sciences. In particular, the quest for efficient algorithms has fueled much research into the structure of
graphs. The importance of spanning trees of various special types, such as breadth-first and depth- first
trees, has become evident, and tree decompositions of graphs are a central ingredient in the theory of
graph minors.
So far we have discussed the tree and its properties when it occurs as a graph by itself. Now we shall
study the tree as a subgraph of another graph. A given graph has numerous subgraphs—from e edges,
2e distinct combinations are possible. Obviously, some of these subgraphs will be trees. Out of these
trees we are particularly interested in certain types of trees, called spanning trees.

Let G be a connected graph, then a subgraph T of G is called Spanning tree (skeleton or scaffolding)
of G if T is a tree and it contains all vertices of G. (i.e. T is spanning subgraph of G)
Note:
¤ Let G be a connected graph and T be a Spanning tree of G, then edges of T are called Branches
of G with respect to T and edges of G which are not in T are called Chords of G with respect to
T
¤ With respect to any of its spanning tree, a connected graph G with n vertices and m edges has
n – 1 branches and m – n + 1 chords.

Page 71
Example:

T1: T2:

In the above example T1 and T2 are spanning trees of G.

It is to be noted that a spanning tree is defined only for a connected graph, because a tree is always
connected, and in a disconnected graph of n vertices we cannot find a connected subgraph with n
vertices. Each component (which by definition is connected) of a disconnected graph, however, does
have a spanning tree. Thus a disconnected graph with к components has a spanning forest consisting
of к spanning trees.

Theorem 6.4.1: Graph G= (V, E) is connected if and only if it has a spanning tree.

Proof: Let G be a connected graph. If G has no cycles, then G is a tree and G itself is spanning tree
of G. If G has cycles, then delete edges from each cycle such that the graph will remain connected. The
resultant graph T is cycle free connected and contains all vertices of G, hence it is a spanningtree
of G. Thus G has a spanning tree.

Conversely, suppose G has a spanning tree T. Since T is connected and has all vertices of G, being a
super-graph of T, the graph G is also connected. This completes the proof.

There are two famous methods of finding a spanning tree of a connected graph. 1) Depth-First Search
(DFS) 2) Breadth-First Search (BFS), We discuss these in detail in the next block

Page 72
 6.5. Summary
A graph G which has no cycles is called an acyclic graph. A forest is an acyclic graph and a connected
acyclic graph is a tree. We can summarize all the characterization of trees discussed in the following
theorem.

Results: The following statements are equivalent for a graph G:

i) G is a tree.
ii) Every two vertices of G are joined by a unique path.
iii) G is connected and p = q + 1.
iv) G is acyclic and p = q + 1.
v) G is acyclic and if any two nonadjacent vertices of G are joined by an edge x, then G + x has
exactly one cycle.
vi) G is connected, is not Kp for p > 3, and if any two nonadjacent vertices of G are joined by an
edge x, then G + x has exactly one cycle.
vii) G is not K3  K1 or K3  K2, p = q + 1, and if any two nonadjacent vertices of G are joined
by an edge x, then G + x has exactly one cycle.

Let D be a directed graph and G be its underlying graph. We say that D is directed tree if G is a
tree. A directed tree T is called rooted tree if i) T contains unique vertex r called the root, whose in-
degree is equal to 0 and ii) The in-degree of all other vertices is equal to 1. Rooted trees play a very
important role in construction of optimal prefix codes.

Let G be a connected graph, then a subgraph T of G is called Spanning tree if T is a tree and it contains
all vertices of G. Edges of T are called Branches of G with respect to T and edges of Gwhich are
not in T are called Chords of G with respect to T . A graph G= (V, E ) is connected if and only if it has
a spanning tree.

6.6. Keywords
Trees, Rooted trees, Binary trees, Spanning trees, Prefix coding

Page 73
6.7. Exercise

1. Prove that a tree with two or more vertices has at least two pendent vertices.

2. Let F = (V, E) be a forest with n vertices, m edges and k components. Prove that n = m + k.

3. Suppose that a tree T has two vertices of degree 2, four vertices of degree 3 and three vertices of
degree 4. Find the number of pendent vertices in T.

4. Define a tree. For a tree T = (V, E) show that 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 pendent
vertices in T.

5. Let T = (V, E) be a complete m-ary tree of height h with l leaves. Then prove that l  mh and
h  log m l  .

6. Let T = (V, E) be a complete m-ary tree with l leaves. Then prove that height of T is log m l  .
7. Find number of leaves and number of internal vertices in a complete 6 – ary tree of order 733.

8. A class room has 25 microcomputers that must be connected to a wall socket that has 4 outlets.
Connections are made using extension chord that has four outlets each. What is the least number
of chords needed to get the computer setup for the class?

9. Define prefix code. Which of the following sets represents prefix code? State reasons
A = {000, 001, 01, 10, 11} B = {1, 00, 01, 000, 0001}

10. Define weighted tree, Optimal tree, and construct optimal prefix code for the symbols a, o, q, u,
y, z that occur with frequencies 20, 28, 4, 17, 12, 7 respectively.

11. Construct optimal prefix code for the symbols a, b, c, d, e, f, g, h, i, j that occur with the
frequencies 78, 16, 30, 35, 125, 31, 20, 50, 80, 3 respectively.

12. Obtain optimal prefix code to send the massage “ROAD IS GOOD” Hence encode the massage.

6.8. References

1. F. Harary, ‘Graph Theory’, Addison-Wesley, 1969

2. Narsingh Deo, ‘Graph Theory with Applications to Engineering and Computer Science’, PHI,
2011.
3. G. Chartrand and L. Lisniak, ‘Graphs and Digraphs’, Wordsworth, [Link], California,
1986.
4. Grimaldi R. Discrete and Combinatorial Mathematics, Pearson, Addison Wesley (2004).

Page 74
 UNIT – 7
CENTERS AND CENTROIDS

Structure:

7.0. Objectives

7.1. Introduction

7.2. Centers and Centroids

7.3. Summary

7.4. Keywords

7.5. Exercises

7.6. References

7.0. Objectives
The objective of this unit is to make the learners conversant on –
 Centrality of trees
 Centroid point of a tree

7.1. Introduction:

For 𝑆 ⊆ 𝑉(𝐺) the S-center and S-centroid of G are defined as the collection of vertices 𝑢 ∈ 𝑉(𝐺) that
minimize 𝑒𝑠 (𝑢) = 𝑚𝑎𝑥 {𝑑(𝑢, 𝑣): 𝑣 ∈ 𝑆} and 𝑑𝑠 (𝑢) = ∑𝑢 ∈ 𝑆 𝑑(𝑢, 𝑣), respectively. This
generalizes the standard definition of center and centroid from the special case of 𝑆 = 𝑉(𝐺). For
1 ⩽ 𝑘 ⩽ |𝑉(𝐺)| and 𝑢 ∈ 𝑉(𝐺). Let 𝑟𝑘(𝑢) = 𝑚𝑎𝑥 {∑𝑠∈𝑆 𝑑(𝑢, 𝑠) : 𝑆 ⊆ 𝑉(𝐺), |𝑆| = 𝑘}. The
𝑘 −centrum of 𝐺, denoted 𝐶(𝐺; 𝑘), is defined to be the subset of vertices 𝑢 in 𝐺 for which 𝑟𝑘 (𝑢) is a
minimum. This also generalizes the standard definitions of center and centroid since 𝐶(𝐺; 1) is the center
and 𝐶(𝐺; |𝑉(𝐺)|) is the centroid.

Page 75
7.2. Centers and centroids:

The eccentricity 𝑒(𝑣) of a point v in a connected graph G is max 𝑑(𝑢, 𝑣) for all u in G. The radius
𝑟(𝐺) is the minimum eccentricity of the points. Note that the maximum eccentricity is the diameter. A
point 𝑣 is a central point if 𝑒(𝑣) = 𝑟(𝐺), and the center of G is the set of all central points.

Fig. 7.2.1. The eccentricities of the points of a tree.

In the tree of Fig. 7.2.1, the eccentricity of each point is shown. This tree has diameter 7, radius
4, and the center consists of the two points u and v, each with minimum eccentricity 4. The fact that u
and v are adjacent illustrates a result discovered by Jordan and independently by Sylvester.

Theorem 7.2.1 Every tree has a center consisting of either one point or two adjacent points.

Proof. The result is obvious for the trees K1 and K2. We show that any other tree T has the same central
points as the tree 𝑇 ′ obtained by removing all endpoints of T. Clearly, the maximum of the distances from
a given point u of 𝑇 to any other point v of T will occur only when v is an endpoint.
Thus, the eccentricity of each point in 𝑇 ′ will be exactly one less than the eccentricity of the same
point in T. Hence the points of T which possess minimum eccentricity in T are the same points having
minimum eccentricity in 𝑇 ′ , that is, T and 𝑇 ′ have the same center. If the process of removing endpoints
is repeated, we obtain successive trees having the same center as T. Since T is finite, we eventually obtain
a tree which is either K1 or K2. In either case all points of this ultimate tree constitute the center of T
which thus consists of just a single point or of two adjacent points.
A branch at a point u of à tree T is a maximal subtree containing u as an endpoint. Thus the number of
branches at u is degu. The weight at a point u of T is the maximum number of lines in any branch at u.

Page 76
The weights at the nonendpoints of the tree in Fig. 7.2.2 are indicated. Of course the weight at each
endpoint is 14, the number of lines.

Fig. 7.2.2. The weights at the points of a tree.

A point v is a centroid point of a tree T if v has minimum weight, and the centroid of T consists
of all such points. Jordan also proved a theorem on the centroid of a tree analogous to his result for centers.

Theorem 7.2.2 Every tree has a centroid consisting of either one point or two adjacent points.

The smallest trees with one and two central and centroid points are shown in Fig. 7.2.3.

Fig. 7.2.3. Trees with all combinations of one or two central and centroid points.

7.3. Summary
Using geometric terminology, we study centrality of trees. This is followed by discussion of tree in
previous unit which is naturally associated with every connected graph; its block-cutpoint tree.

7.4. Key Words: Centers and Centroids

Page 77
7.5. Exercises:

1. Construct a tree with disjoint center and centroid, each having two points.

2. The center of any connected graph lies in a block.

7.6. References

1. F. Harary, ‘Graph Theory’, Addison-Wesley, 1969

2. Narsingh Deo, ‘Graph Theory with Applications to Engineering and Computer Science’, PHI,
2011.
3. G. Chartrand and L. Lisniak, ‘Graphs and Digraphs’, Wordsworth, [Link], California,
1986.
4. Grimaldi R. Discrete and Combinatorial Mathematics, Pearson, Addison Wesley (2004).

Page 78
 UNIT – 8
INDEPENDENT CYCLES AND COCYCLES

Structure:

8.0. Objectives

8.1. Introduction

8.2. Independent cycles and Cocycles

8.3. Summary

8.4. Keywords

8.5. References

8.0. Objectives
The objective of this unit is to make the learners conversant on –
 Independent cycles
 Cocycles

8.1. Introduction

We describe two vector, spaces associated with a graph G: its "cycle space" and "cocycle space." For
convenience, these two vector spaces will be taken over the two element field F2 = {0, 1}, in which 1 +
1= 0 {even though the theory can be modified to hold for an arbitrary field). In particular, the ε i, which
occur repeatedly in the following definitions are always either 0 or 1.

As usual, let G be a graph with points 𝑣1 , … , 𝑣𝑝 and lines 𝑥1 , … … , 𝑥𝑞 A 0-chain of G is a formal linear
combination ∑ 𝜀𝑖 𝑥𝑖 of points and a I-chain is a sum ∑ 𝜀𝑖 𝑥𝑖 of lines. The boundary operator ∂ sends 1-
chains to 0-chains according to the rules:

a) ∂ is linear.
b) If 𝑥 = 𝑢𝑣, then ∂x = u + v.

Page 79
On the other hand, the coboundary operator ∂ sends 0-chains to 1-chains by the rules :
a) ∂ is linear.
b) ∂u = ∑ 𝜀𝑖 𝑥𝑖 Where εi = l whenever xi, is incident With v.

Fig. 8.1.1. A graph to illustrate the boundary and coboundary operators.

In Fig . 8.1.1, the 1-chain σ1 = x1 + x2+ x4 + x9 has boundary

∂σ1 =( v1, + v2) + (v1 + v3) + (v2 + v4) + (v5 + v6)
= v3 + v4 + v5 + v6
and the 0-chain σ0 = v3 + v4 + v5 + v6 has as its coboundary
∂σ0 = (x2 + x3 + x6 + x7) +(x4 + x8)
(x5 + x6 + x8 + x9) +(x7 + x9)
= x2 + x3 + x4 + x5
Á 1-chain with boundary O is a cycle vector* of G and can be regarded as a set of line-disjoint cycles.
The collection of all cycle vectors forms a vector space over F2 called the cycle space of G. A cycle basis
of G is defined as a basis for the cycle space of G which consists entirely of cycles. We say a cycle-vector
Z depends on the cycles Z1, Z2, …, Zk, if it can be written as ∑𝑘𝑖 = 1 𝜀𝑖 𝑍𝑖 Thus a cycle basis of G is a
maximal collection of independent cycles of G, or a minimal collection of cycles on which all cycles
depend.
A cutest of a connected graph is a collection of lines whose removal results in a disconnected
graph. A cocycle is a minimal cutset. A coboundary of G is the coboundary of some 0-chain in G. The
coboundary of a collection U of points is just the set of all lines joining a point in U to a point not in U.
Thus every coboundary is a cutset. Since we define a cocycle as a minimal cutsét of G and any minimal
cutset is a coboundary, we see that a cocycie is just a minimal nonzero coboundary. The collection of all
coboundaries of G is called the cocycle space of G, and a basis for this space which consists entirely of

Page 80
cocycles is called a cocycle basis for G.

We proceed to construct for the cycle space of G a basis which corresponds to a spanning tree T.
In a connected graph G, a chord of a spanning tree T is a line of G which is not in T. Clearly the subgraph
of G consisting of T and any chord of. T has exactly one cycle. Moreover, the set Z(T)

8.2. Independent cycles and cocycles

Fig. 8.2.1 Graph, tree, and cotree.

Fig. 8.2.2. A cocycle basis for G of Fig. 8.2.

of cycles obtained in this way (one from each chord) is independent, since each contains a line not in any
of the others. Also, every cycle Z depends on the set Z(T), for Z is the symmetric difference of the cycles
determined by the chords of T which lie in Z. Thus if we define m(G), the cycle rank, to be the number
of cycles in a basis for the cycle space of G, we have the following result.

Theorem 8.2.1 The cycle rank of a connected graph G is equal to the number of chords of any spanning
tree in G.

Corollary 8.2.1(a) If G is a connected (p, q) graph, then 𝑚(𝐺) = 𝑞 − 𝑝 + 1.

Corollary 8.2.1(b) If G is a (𝑝, 𝑞) graph with k components, then

𝑚(𝐺) = 𝑞 − 𝑝 + 𝑘.

Similar results are true for the cocycle space. The cotree T* of a spanning tree T in a connected
graph G is the spanning subgraph of G containing exactly those lines of G which are not in T. A cotree
of G is the cotree of some spanning tree 1. In Fig. 8.2.1, a spanning tree T and its cotree T* are displayed

Page 81
for the same graph G as in Fig. 8.2.2. The lines of G which are not in T* are called its twigs. The subgraph
of G consisting of T* and any one of its twigs contains exactly onc cocycle. The collection of cocycles
obtained by adding twigs to T*, one at a time, is seen to be a basis for the cocycle space of G. This is
illustrated in Fig. 8.2.2. for the graph G and cotree T* of Fig, 8.2.1, with the cocycles indicated by heavy
lines. The cocycle rank 𝑚(𝐺) is the number of cocycłes in a basis for the cocycłe space of G.

Theorem 8.2.2 The cocycle rank of a connected graph G is the number of twigs in any spanning tree of
T.
As in the case of cycles, we have two immediate corollaries.
Corollary 8.2.2 (a) If G is a connected (𝑝. 𝑞) graph, then 𝑚*(𝐺) = 𝑝 − 1.
Corollary 8.2.2 (b) If G is a (p, g) graph with k components, then 𝑚*(𝐺) = 𝑝 − 𝑘.
Excursion
The 1-dimensional case of an important general result about simplicial complexes can be derived from
Theorem 8.2.3 The Euler-Poincare equation

∝0 + ∝1 + ∝2 … = β0 + β1 + β2 …

where the βn are the Betti numbers and the a, are the numbers of simplexes of cach dinnension, holds for
every simplicial compiex. Reca!! irom Chapter 1 that every graph is a simplicial compiex, with its points
0-simpiexes and its lines i-simplexes. For a graph, β0 = k, the number of connected componenis, and β1
= m{G), the number of independent cycłes of G. Since no graph contains an n-simplex with n > 1, ∝n =
βn = 0, for all n > 1. Thus ∝0 - ∝1 = β0 – βi so p - q = k – m(G) and we see that Corollary 8.2.2(b) is the
Euler-Poincare equation for graphs.

8.3. Summary
In this unit we see how each spanning tree of a graph G gives rise to a collection of independent cycles
of G, and mention the dual (Complementary) construction of a collection of independent cocycles from
each spanning cotree.

8.4. Key Words: Independent cycles and Cocycles.

8.5. References

1. F. Harary, ‘Graph Theory’, Addison-Wesley, 1969

2. Narsingh Deo, ‘Graph Theory with Applications to Engineering and Computer Science’, PHI,
2011.
3. G. Chartrand and L. Lisniak, ‘Graphs and Digraphs’, Wordsworth, [Link], California,
1986.
4. Grimaldi R. Discrete and Combinatorial Mathematics, Pearson, Addison Wesley (2004).

Page 82
 BLOCK III

CONNECTIVITY

Page 83
 UNIT – 9

CONNECTIVITY AND EDGE CONNECTIVITY

Structure:

9.0. Objectives

9.1. Introduction

9.2. Connectivity and edge connectivity

9.3. Summary

9.4. Keywords

9.5. Exercises

9.6. References

9.0. Objectives

The objective of this unit is to make the learners conversant on –

 Connectivity (vertex-connectivity), Edge-connectivity.

9.1. Introduction

The connectivity of graphs is a particularly intuitive area of graph theory and extends the concepts of
cut-vertex, bridge, and block. Two invariants called connectivity and edge-connectivity are useful in
deciding which of two graphs is more connected. There are many theorems concerning connectivity
and edge connectivity.

9.2. Connectivity and Edge-Connectivity

The connectivity (vertex connectivity) к = к (G) of a graph G is the minimum number of vertices whose
removal results in a disconnected or trivial graph. Thus the connectivity of a disconnected graph is 0,
while the connectivity of a connected graph with a cut-vertex is 1. The complete graph Kp cannot be
disconnected by removing any number of vertices, but the trivial graph results after removing p – 1

Page 84
vertices. Therefore, к(Kр) = p – 1. Sometimes к is called the vertex-connectivity.

Analogously, the edge-connectivity (line-connectivity)  = (G) of a graph G is the minimum number

of edges whose removal results in a disconnected or trivial graph. Thus (K1) = 0 and the edge-
connectivity of a disconnected graph is 0, while that of a connected graph with a bridge is 1.
Connectivity, edge – connectivity and minimum degree are related by an inequality due to Whitney,
which is given by the following theorem.

Theorem 9.2.1: For any graph G,  (G)  (G)   (G).

Proof: We first verify the second inequality. If G has no edges, then  = 0. Otherwise, a disconnected
graph results when all the edges incident with a vertex of minimum degree are removed. In either case,
 ≤ .

To obtain the first inequality, various cases are considered. If G is disconnected or trivial, then
к =  = 0. If G is connected and has a bridge x, then  = 1. In this case, к = 1 since either G has a cut-
vertex incident with x or G is K2. Finally, suppose G has  ≥ 2 edges whose removal disconnects it.
Clearly, the removal of  – 1 of these edges produces a graph with a bridge x = uv. For each of these
 – 1 edges, select an incident vertex different from u or v. The removal of these vertices also removes
the  – 1 edges and quite possibly more. If the resulting graph is disconnected, then к < ; if not, x is
a bridge, and hence the removal of u or v will result in either a disconnected or a trivial graph, so к  
in every case. (See Figure 9.2.1).

Figure 9.2.1: A graph with к = 2,  = 3 and  = 4

Page 85
 Note: Chartrand and Harary constructed a family of graphs with prescribed connectivities which also
have a given minimum degree. This result shows that the restrictions on к,  and  imposed by above
Theorem cannot be improved.

Theorem 9.2.2: For all integers a, b, с such that 0 < a  b  c, there exists a graph G with к (G) = a,

(G)  b , and  (G)  c.

𝑝
Theorem 9.2.3: If G has p vertices and  (G) ⌈2⌉then  G   G .
𝑝
Note: If G is regular of degree r ≥ 2, then (G) = r. In particular,  (Kp) = p – 1.

It is premature stage to have a look on the proofs of Theorems 9.2.2 and 9.2.3, as it needs to be studied

at the advanced level of learning. Chartrand pointed out that if  (G is large enough, then the second
inequality of Theorem 9.2.1 becomes equality. The analogue of Theorem 9.2.3 forconnectivity does
not hold. The problem of determining the largest connectivity possible for a graph with a given number
of vertices and edges was proposed by Berge.

Theorem 9.2.4: Among all graphs with p vertices and q edges, the maximum connectivity is 0 when
2𝑞
q < p – 1 and is ⌈ 𝑝 ⌉ , when q ≥ 𝑝 − 1.

2𝑞
Outline of proof. Since the sum of the degrees of any (𝑝, 𝑞) graph 𝐺 is 2𝑞, the mean degree is .
𝑝
2𝑞 2𝑞
Therefore,  (G) ≤⌈ 𝑝 ⌉so𝜅(𝐺)) ≤ ⌈ 𝑝 ⌉by the Theorem 9 .2.1. To show that this value can actually

be attained, an appropriate family of graphs can be constructed. The same construction also gives those
(p, q) graphs with maximum edge-connectivity.

Page 86
Corollary 9.2.5: The maximum edge-connectivity of a (p, q) graph equals the maximum
connectivity.

A connectivity pair of a graph G is an ordered pair (a, b) of nonnegative integers such that
there is some set of a vertices and b edges whose removal disconnects the graph and there is
no set of a – 1 vertices and b edges or of a vertices and b – 1 edges with this property. Thus
in particular the two ordered pairs (к, 0) and (0, ) are connectivity pairs for G, so that the
concept of connectivity pair generalizes both the point-connectivity and the edge-connectivity
of a graph.

The connectivity pairs of a graph G determine a function f from the set {0, 1, . . . , к} into
the nonnegative integers such that f (к) = 0 (Refer, Theorem 9.2.1). This is called the
connectivity function of G. It is strictly decreasing, since if (a, b) is a connectivity pair
with b > 0 there is obviously a set of a + 1 vertices and b – 1 edges whose removal
disconnects the graph or leaves only one vertex. The following theorem proved by
construction by Beineke and Harary, shows that these are the only conditions which a
connectivity function must satisfy.

Theorem 9.2.6. Every decreasing function f from {0, 1, . . ., к} into the non-negative
integers such that f (к) = 0 is the connectivity function of some graph.

A graph G is n-connected if к (G) ≥ n and n-edge-connected if  (G) ≥ n. We note that a

nontrivial graph is 1-connected if and only if it is connected, and that it is 2-connected if and
only if it is a blockhaving more than one edge. So K2 is the only block not 2-connected.

Note:

¤ G is 2-connected if and only if every two vertices of G lie on a cycle.

¤ If G is n-connected, n ≥ 2, then every set of n vertices of G lie on a cycle.

(Generalization ofthe above note

Characterizations of n-connected graphs lead to an advanced study on this topic, the

interested onemay opt for further study.

9.3. Summary
The connectivity (vertex connectivity) к = к (G) of a graph G is the minimum number of

Page 87
 vertices whose removal results in a disconnected or trivial graph. The edge-connectivity
(line-connectivity)  = (G) of a graph G is the minimum number of edges whose removal
results in a disconnected or trivial graph. For any graph G,  (G)  (G)   (G).

A connectivity pair of a graph G is an ordered pair (a, b) of nonnegative integers such that
there is some set of a vertices and b edges whose removal disconnects the graph and there is
no set of a – 1 vertices and b edges or of a vertices and b – 1 edges with this property. The
connectivity pairs of a graph G determine a function f from the set {0, 1, . . . , к} into the
nonnegative integers such that f (к)= 0. This is called the connectivity function of G.

A graph G is n-connected if к (G) ≥ n and n-edge-connected if  (G) ≥ n. We note that a

nontrivial graph is 1-connected if and only if it is connected, and that it is 2-connected if and
only if it is a blockhaving more than one edge. So K2 is the only block not 2-connected.

9.4. Keywords
Connectivity, Vertex connectivity, Edge-connectivity.

9.5. Exercises
1. Construct a graph with к = 3,  = 4,  = 5.
2. Show that there exists no 3-connected graph with seven edges.
3. Show that the connectivity and edge connectivity are equal in every cubic graph.

9.6. References

1. F. Harary, ‘Graph Theory’, Addison-Wesley, 1969

2. G. Chartrand and L. Lisniak, ‘Graphs and Digraphs’, Wordsworth, [Link],
California,1986.

Page 88
 UNIT – 10
WHITNEY’S THEOREM

Structure:

10.0 Objectives

10.1 Introduction

10.2 Whitney’s Theorem

10.3 Keywords

10.4 References

10.0. Objectives

The objective of this unit is to make the learners conversant on –

 Whitney’s Theorem on connectivity

10.1 Introduction
Let ∆ = (𝑉, 𝐸) be an ordinary graph, i.e. a graph without loops or multiple edges.
So, we can consider each edge 𝑒 ∈ 𝐸 as a set of two distinct vertices. Then its line graph
𝐿(∆) is the graph with vertex set E and two vertices 𝑒, 𝑓 ∈ 𝐸 adjacent if and only if
they intersect in a single vertex of ∆.The graph ∆ is called a root graph for its line
graph.
An isomorphism φ between two graphs ∆ = (𝑉, 𝐸) and ∆’ = (𝑉 ′ , 𝐸 ′ ) is a bijection 𝜑 ∶
𝑉 → 𝑉 ′ , such that the map on E induced by φ, i.e. ∅({𝑉, 𝑊})={∅(𝑉), ∅(𝑊)} for
all {𝑉, 𝑊} ∈ 𝐸, is a bijection from E to 𝐸 ′ .
Clearly, if φ is an isomorphism between two graphs ∆ = (𝑉, 𝐸) and ∆’ = (𝑉 ′ , 𝐸 ′ ), then φ
induces also an isomorphism between the two line graphs 𝐿(∆) and 𝐿(∆′ )
Whitney’s Theorem is concerned with the reverse problem:
An isomorphism between line graphs of graphs ∆ and ∆′ also imply the existence of an
isomorphism between ∆ and ∆′ .

Page 89
In other words, the root graph of a line graph is unique.

10.2 Whitney’s Theorem for Line Graphs Of Multi-Graphs

Whitney’s Theorem states that every graph, different from K3 or K1,3, is

uniquely determined by its line graph. A 1-line graph of a multi- graph is the
graph with as vertices the edges of the multi-graph, and two edges adjacent if and
only if there is a unique vertex on both edges. The 1-line graph of a multi-graph
is the graph on the edges of the multi-graph, where two edges are adjacent if and
only if there is at least one vertex on both edges. We extend Whitney’s theorem
to such line graphs of multi-graphs, and show that most multi-graphs are uniquely
determined by their line graph. Moreover, we present an algorithm to determine
for a given graph Γ, if possible, a multi - graph with Γ as line graph.

Theorem 10.2.1 (Whitney’s Theorem): Suppose ∆ and ∆′ are connected graphs and φ an
isomorphism between the line graph 𝐿(∆) and 𝐿(∆′ ).
Proof: Consider an unique isomorphism ψ between ∆ and ∆′ , inducing φ, unless ∆ and
∆′ are K1,3 and K3.
we consider the same for multi-graphs. Here a multi-graph
∆ = (𝑉, 𝐸) consists of a set of vertices V and a set of edges E together with a relation
~ between V and E such that for any element 𝑒 ∈ 𝐸 there are exactly two distinct
elements 𝑣, 𝑤 ∈ 𝑉 with 𝑣, 𝑤~ 𝑒. 𝐼𝑓 𝑣~𝑒, then we will say 𝑣 is one. Of course, an
ordinary graph is a multi-graph in which the relation ~ is the relation ∈.

There are at least two different obvious choices for the definition of the line graph of a multi-
graph. The vertices of the line graph of ∆ = (𝑉, 𝐸) are the elements from E. But two
elements 𝑒, 𝑓 ∈ 𝐸 can be defined to be adjacent if and only if there is a unique vertex
with ~ 𝑒 𝑎𝑛𝑑 𝑣 ~ 𝑓 , or, if and only if there is at least one vertex 𝑣 with 𝑣 ~ 𝑒 and
𝑣 ~𝑓 . We consider both situations.
The 1-line graph 𝐿1 (∆)of a multi-graph ∆ is the graph with vertex set E, such that two
vertices 𝑒, 𝑓 ∈ 𝐸 are adjacent if and only if there is a unique vertex v of ∆ with 𝑣 ~ 𝑒
and ~ 𝑓 . By 𝐿 ≥ 1(∆)we denote the ≥ 1-line graph of ∆, the graph with vertex

Page 90
set E and two edges e, f adjacent if there is a at least one vertex v of ∆ with 𝑣 ~ 𝑒
and 𝑣 ~𝑓 .
If it is clear from the context whether we are considering the 1-line graph or ≥ 1-line
graph, we will just refer to these graphs as line graphs. In both cases the graph ∆ is
called a root graph for its line graph. An isomorphism between two multi-∆ =
(𝑉, 𝐸)𝑎𝑛𝑑∆, = (𝑣 ′ , 𝐸′) is a pair ((∅𝑣, ∅𝐸) of bijections such that for all 𝑣 ∈ 𝑉𝑎𝑛𝑑 𝑒 ∈
𝐸 we have
𝑣~𝑒 ↔ ∅𝑣(𝑣)~∅𝐸(𝑒)
An isomorphism between two multi-graphs ∆ = (𝑉, 𝐸) and ∆, = (𝑣 ′ , 𝐸′) induces an
isomorphism ∅𝐸 between two graphs 𝐿1 (∆)𝑎𝑛𝑑 𝐿1 (∆′ )..

Theorem 10.2.2. Suppose ∆ and ∆′ are connected multi-graphs and φ an isomorphism

between the line graph 𝐿1 (∆)𝑎𝑛𝑑 𝐿1 (∆′ ).
Then there is a unique isomorphism between ∆ and ∆′ , inducing φ, unless ∆ or ∆′
contains four vertices.
Moreover, up to isomorphism, there is a unique connected multi-graph ∆′′ , not on 4
vertices, such that 𝐿1 = ∆′′ is isomorphic to 𝐿1 (∆)𝑎𝑛𝑑 𝐿1 (∆′ ).

Theorem 10.2.3. Suppose ∆ and ∆′ are connected multi-graphs and φ an isomorphism

between the line graph 𝐿≥ (∆)𝑎𝑛𝑑 𝐿≥ (∆′ ). Then there is a unique isomorphism between
∆ and ∆′ , inducing φ, unless ∆ or ∆′ contains a subgraph ∆0
x

y
such that the vertices x and y have no other neighbors outside ∆0.
Moreover, up to isomorphism, there is a unique connected multi-graph ∆′′ not
containing such subgraph ∆0, with𝐿≥ (∆′′ ).isomorphic to 𝐿≥ (∆)𝑎𝑛𝑑 𝐿≥ (∆′ ).

10.3. Keywords: Whitney’s Theorem on connectivity

Page 91
10.4. References
1. F. Harary, ‘Graph Theory’, Addison-Wesley, 1969

2. G. Chartrand and L. Lisniak, ‘Graphs and Digraphs’, Wordsworth, [Link],

California,1986.

Page 92
 UNIT – 11

MENGER’S THEOREM

Structure:

11.0. Objectives

11.1. Introduction

11.2. Menger’s Theorem

11.3. Dirac’s Theorem

11.4. Hall’s Theorem, Max Flow Min Cut Theorem

11.5. Summary

11.6. Keywords

11.7. Exercises

11.8. References

Page 93
11.0 Objectives

The objective of this unit is to make the learners conversant on –

 Graphical variations of Menger’s Theorem.

 Dirac’s Theorem

 Hall’s Theorem and Max flow min cut theorem.

11.1 Introduction

In 1927 Menger showed that the connectivity of a graph is related to the number of disjoint paths joining
distinct vertices in the graph. Many of the variations and extensions of Menger’s result which have since
appeared have been graphical, and we discuss some of these here. By emphasizing the form these
theorems take, it is possible to classify them in an illuminating way.

11.2. Menger’s theorem:

Menger’s theorem states that the maximum number of pairwise internally disjoint paths between a
given pair of non-adjacent vertices in a graph equals the minimum numberof vertices whose deletion
disconnects the pair. Thus, the maximum number of pairwise internally disjoint paths that connect a
given pair of vertices is a local measure that indicates how well a given pair of vertices is connected.
The connectivity of a graph is the minimum number of vertices whose deletion disconnects the graph
and can be expressed in terms of the connectivity between pairs of vertices.

Let u and v be two distinct vertices of a connected graph G. Two paths joining u and v are called
disjoint (sometimes called vertex-disjoint) if they have no vertices other than u and v (and hence no
edges) in common; they are edge-disjoint if they have no edges in common. A set S of vertices, edges,
or vertices and edges separates u and v if u and v are in different components of G – [Link],
no set of vertices separates two adjacent vertices. Menger’s Theorem was originally presented in the
“vertex form” given in following theorem.

Theorem 11.2.1: The minimum number of vertices separating two nonadjacent vertices s and t is the
maximum number of disjoint s-t paths.

Menger discovered his result in the course of research he was conducting in the theory of curves in
point-set topology. However, as Konig pointed out, Menger’s original proof has a significant gap. The
first flawless proof was provided by Noebeling. Presently there are several proofs are available due to
Konig , McCuaig, Ore, Ford and Fulkerson etc. We follow the elegant proof of Dirac.

Proof: It is clear that if k vertices separate s and t, then there can be no more than к disjoint paths
Page 94
joining s and t.

It remains to show that if it takes k vertices to separate s and t in G, there are k disjoint s-t paths in G.
This is certainly true if k = 1. Assume it is not true for some k > 1. Let h be the smallest such k, and F
be a graph with the minimum number of vertices for which the theorem fails for h. We remove edges
from F until we obtain a graph G such that h vertices are required to separate s and t in G but for any
edge x of G, only h – 1 vertices are required to separate s and t in G – x. We first investigate the
properties of this graph G, and then complete the proof of the theorem.

Claim I: No vertex is adjacent to both s and t in G.

By the definition of G, for any edge x of G there exists a set S (x) of h – 1 vertices which separates
s and t in G – x. Now G — S (x) contains at least one s-t path, since it takes h vertices to separate
s and t in G. Each such s-t path must contain the edge x = uv since it is not a path in G – x.
So 𝑢, 𝑣 ∉ 𝑆 (𝑥) and if 𝑢 ≠ 𝑠, 𝑡 then 𝑆 (𝑥) ∪ {𝑢} separates s and t in G.

If there is a point w adjacent to both s and t in G, then G – w requires h – 1 vertices to separate s and t
and so it has h – 1 disjoint s-t paths. Replacing w, we have h disjoint s-t paths in G. Hence we proved
the claim I.

Claim II: Any collection W of h vertices separating s and t is adjacent either to s or to t.

Let W be any collection of h vertices separating s and t in G. An s-W path is a path joining s with some
wi ∈ W and containing no other vertex of W. Call the collections of all s-W paths and W-t paths Ps and
Pt respectively. Then each s-t path begins with a member of Ps and ends with a member of Pt, because
every such path contains a vertex of W. Moreover, the paths in Ps and Pt have the vertices of W and no
others in common, since it is clear that each wi is in at least one path in each collection and,if some
other vertex were in both an s-W and a W-t path, then there would be an s-t path containingno vertex
of W. Finally, either Ps – W = {s} or Pt – W = {t}, since, if not, then both Ps plus the edges
{w1 t, w2t,...} and Pt plus the edges {sw1 sw2, . . . } are graphs with fewer vertices than G in whichs
and t are nonadjacent and h-connected, and therefore in each there are h disjoint s-t paths. Combining
the s-W and W-t portions of these paths, we can construct h disjoint s-t paths in G, and thus have a
contradiction. Therefore, claim II holds.

Now we can complete the proof of the theorem.

Let 𝑃 = {𝑠, 𝑢1, 𝑢2,…, t} be a shortest s-t path in G and let u1u2 = x . Note that by claim u2  t .

Form 𝑆(𝑥) = {𝑣1 , 𝑣2 , … , 𝑣ℎ−1 } as above, separating s and t in G-x. By claim I, u1tG , so by claim

II, with W = S(x) {{u1} , svi G , for all i. Thus by claim I, vit G , for all i. However, if we pick

W = S(x) {u2} instead, we have by claim II that su2 G , contradicting our choice of P as a
Page 95
 shortest s-t path, and completes the proof of the theorem.

Figure 11.2.1: A graph illustrating Menger’s Theorem.

In Figure 11.2.1, we display a graph with two nonadjacent vertices s and t which can be separated by
removing three vertices but no fewer. In accordance with the theorem, the maximum number of disjoint
s – t paths is 3.
Chronologically the second variation of Menger’s Theorem was published by Whitney, in which he
included a criterion for a graph to be n – connected.

Theorem11.2.2: A graph is n-connected if and only if every pair of vertices are joined by at least n

vertex-disjoint paths.
An indication of the relationship between Theorems 11.2.1 and 11.2.2 is easily supplied by introducing
the concept of local connectivity. The local connectivity of two nonadjacent vertices u and v of a graph
is denoted by к (𝑢, 𝑣) and is defined as the smallest number of vertices whose removal separates
u and v. In these terms, Menger's Theorem asserts that for any two specific nonadjacent

vertices 𝑢 and 𝑣, к (𝑢, 𝑣) = 𝜇0 (𝑢, 𝑣) the maximum number of vertex-disjoint paths joining u and v.

Both theorems hold obviously for complete graphs. If we are dealing with a graph G which is not
complete, then the observation which links Theorems 11.2.1 and 11.2.2 is that к (G) = min к (u, v) over
all pairs of nonadjacent points u and v.

Page 96
 Strangely enough, the theorem analogous to Theorem 11.2.1 in which the pair of vertices are separated
by a set of edges was not discovered until much later. There are several nearly simultaneousdiscoveries
of this result which appeared recently, we quote the following theorems for the firmness of
completeness.

Theorem 11.2.3: For any two vertices of a graph, the maximum number of edge-disjoint paths joining
them equals the minimum number of edges which separate them.

Note: Referring again to Figure 11.2.1, we see that s and t can be separated by the removal of five
edges but no fewer, and that the maximum number of edge-disjoint u-v paths is five.

Thus we see that with no additional effort we can get another variation of Menger's Theorem by stating
the edge form of the Whitney result (Theorem 11.2.2). Hence the following theorem.

Theorem 11.2.4: A graph is n-edge-connected if and only if every pair of vertices are joined by at
least n edge-disjoint paths.

In Menger's original paper there also appeared the following variation involving sets of vertices rather
than individual vertices.

Theorem11.2.5: For any two disjoint nonempty sets of vertices V1 and V2, the maximum number
disjoint paths joining V1 and V2 is equal to the minimum number of vertices which separate
V1 and V2.

Another variation is given in the next theorem, considered by Dirac. Because the proof involves typical
methods in the demonstration of equivalence of these variations, we include it in full.

Theorem 11.2.6: A graph with at least 2n vertices is n-connected if and only if for any two disjoint
sets V1 and V2 of n vertices each, there exist n disjoint paths joining these two sets of vertices.

[Note that in this theorem these n disjoint paths do not have any vertices at all in common, not even
their end vertices!]

Proof: To show the sufficiency of the condition, we form the graph G' from G by adding two new

Vertices 𝑤1 and 𝑤2 with 𝑤𝑖 adjacent to exactly the vertices of 𝑉𝑖 . 𝑖 = 1,2. (See Figure 11.2.2).

Since 𝐺 is n-connected, so is G', and hence by Theorem 10.2.1, there are n disjoint paths joining
𝑤1 and 𝑤2 . The restrictions of these paths to G are clearly the n disjoint 𝑉1 − 𝑉2 paths we need.

To prove the other half, let S be a set of a least n-1 vertices which separates G into 𝐺1 and 𝐺2 with vertices
sets 𝑉1 ′ and 𝑉2 ′ respectively. Then, since |𝑉1 ′ | ≥ 1, |𝑉2 ′ | ≥ 1, and |𝑉1 ′ | + |𝑉2 ′ | + |𝑉| ≥ 2𝑛, there is a
partition of S into two disjoint subsets 𝑆1 and 𝑆2 such that |𝑉1 ′ ∪ 𝑆1 | ≥ 𝑛 and |𝑉2 ′ ∪ 𝑆2 | ≥ 𝑛. Picking
any n-subsets 𝑉1 of 𝑉1 ′ ∪ 𝑆1 and 𝑉2 of 𝑉2 ′ ∪ 𝑆2 , we have two disjoint sets of n vertices each.

Page 97
 Every path joining 𝑉1 and 𝑉2 must contain a point of S, and since we know there are n disjoint
𝑉1 − 𝑉2 paths, we see that |𝑆| ≥ 𝑛, and 𝐺 is 𝑛 −connected.

𝑉1 𝑉2
G:
G

w1 w2

Figure 11.2.2: Construction of 𝐺 ′

We have defined connectivity pairs for a graph. Similarly, one can define connectivity pairs
for two specific vertices 𝑢 and 𝑣. It is then natural to ask for a mixed form of Menger’s
Theorem involving connectivity pairs. The following theorem of Beineke and Harary is one
such result; a proof can be readily supplied by imitating that of theorem 10.2.1.

Theorem 11.2.7: The ordered pair (a, b) is a connectivity pair for vertices u and v in a graph
G if and only if there exist a vertex-disjoint 𝑢 – 𝑣 paths and also b edge disjoint 𝑢 − 𝑣 paths
which are edge disjoint from the preceding a paths, and further these are the maximum
possible numbers of such paths. Finally, Fulkerson proved the following theorem, which deals
with disjoint cut-sets instead of disjointpaths.

Theorem 11.2.8: In any graph, the maximum number of edge-disjoint cut-sets of edges
separating twovertices 𝑢 and 𝑣 is equal to the minimum number of edges in a path joining u
and v; that is, to d (𝑢, 𝑣).

Although this theorem is of Mengerian type, it is much easier to prove than Menger’s
Theorem. By taking all the possible variations of this theorem, as we have with the theorems
involving paths, we could increase the number of Mengerian theorems again. For Further
Variations of Menger’s theorems interested readers can go for advanced study.

Page 98
11.3. Dirac’s Theorem

Recall that a Hamiltonian cycle in a graph 𝐺 = (𝑉, 𝐸)is a cycle that visits each
vertex exactly once. Unlike for Euler cycles, no simple characterization of graphs with
Hamiltonian cycles is known. In fact, the question whether a given graph has a
Hamiltonian cycle is known to be NP-complete – a technical term that, for all practical
purposes, implies that this question cannot be solved efficiently.

Some conditions that imply the existence of Hamiltonian cycles are known though. A
rather obvious intuition is that if a graph is sufficiently dense (has enough edges) then
it should have long cycles. The theorem below shows that this intuition is indeed right.

Theorem 11.3.1 (Dirac’s theorem) Let 𝐺 = (𝑉, 𝐸) be a graph with n vertices in

which each vertex has degree at least n/2. Then 𝐺 has a Hamiltonian cycle.

Proof: The proof is by an explicit construction, that is, we show that if 𝐺 satisfies
the condition in the theorem that we can construct a Hamiltonian cycle in 𝐺.

The idea is to pick some vertex v1 arbitrarily and gradually extend a path P starting
from v1, say 𝑃 = 𝑣 1𝑣 2. . . 𝑣𝑘 , where all vertices vj are different. Eventually, if 𝑘 =
𝑛, 𝑃 will be a Hamiltonian path.

Initially, 𝑃 = (𝑣1). Suppose that we have already constructed 𝑃 = 𝑣 1𝑣 2. . . 𝑣𝑘 . We

now show that as long as 𝑘 < 𝑛 we can always extend 𝑃. If 𝑣𝑘 has a neighbor 𝑢 ∈ 𝑉
that is not on 𝑃 , then it is easy to extend 𝑃 , for we can simply append u at the end of
𝑃. In other words, we can take 𝑣𝑘+1 = 𝑢 and the new extended path will
be 𝑣 1𝑣 2. . . 𝑣𝑘 𝑣𝑘+1

The second case is when all neighbors of vk are on 𝑃. This case is a bit more tricky.
The idea is this: We will show that there is a neighbor 𝑣𝑗 of 𝑣𝑘 uch that 𝑣𝑗 +1 has a
neighbor outside 𝑃. Then we will perform a switch operation that transforms 𝑃 into
the following path: 𝑣 1𝑣 2. . . 𝑣𝑗 𝑣𝑘 𝑣𝑘 − 1. . 𝑣𝑗 +1𝑢, as in the figure below:

Vj vk

v1
u vj+1
v2

Page 99
 switch

v1 vj vk
vj+1
v2
u
Figure 11.3.1
Notice that the new path is indeed longer than 𝑃 by one vertex.

It is now sufficient to prove that such vertex 𝑣 j always exists. Since all neighbors of
𝑣𝑘 are on P and are different than vk , we have 𝑘 − 1 ≥ 𝑑𝑒𝑔(𝑣𝑘 ) ≥ 𝑛/2, so 𝑘 ≥
𝑛/2 + 1. For each neighbor vj of vk , we mark the next vertex on P , that is vj +1.
Since all neighbors of 𝑣𝑘 are on 𝑃 , this way we will mark deg(vk ) vertices.
Consider any vertex u not on P. If none of u’s neighbors were marked, then by adding
the numbers of u’s neighbors, the marked vertices, and u itself, we would get that the total
number of vertices in G is at least 𝑑𝑒𝑔(𝑢) + 𝑑𝑒𝑔(𝑣𝑘 ) + 1 ≥ 𝑛/2 + 𝑛/2 + 1 >
𝑛 a contradiction. Therefore, there must be a marked vertex that is a neighbor of u. But
this means, exactly, that there will be a vertex vj as in the figure above, and the switch
operation can be applied.
Summarizing what we’ve done so far, the above argument shows that 𝑣 has a
Hamiltonian path 𝑃 = 𝑣1𝑣 2. . . 𝑣n. But the theorem actually says that 𝐺 has a
Hamiltonian cycle, so we are not really done yet. This is left as an exercise. In other
words, you need to show how (under three assumptions from the theorem) you can convert
𝑃 into a Hamiltonian cycle.

11.4. Hall’s Theorem, Max Flow Min Cut Theorem

11.4.1. Hall’s Marriage Theorem or Hall’s Theorem:

Statement: If G is a bipartite graph with bipartition sets V1 and V2, then there exists a matching
which saturates V1 if and only if, for every subset X of V1, | X | ≤ |A(X)|.
Proof. It remains to prove that the given condition is sufficient, so we assume that | X | ≤ |A(X)|
for all subsets X of V1.
In particular, this means that every vertex in V1 is joined to at least one vertex in V2 and also
that | V1 | ≤ | V2 |.
Assume that there is no matching which saturates all vertices of V1. We derive a contradiction.

Page 100
We turn G into a directed network in exactly the same manner as with the job assignment
application.
Specifically, we adjoin two vertices s and t to G and draw directed arcs from s to each vertex
in V1 and from each vertex in V2 to t.
Assign a weight of 1 to each of these new arcs. Orient each edge of G from its vertex in V1 to
its vertex in 𝑉2, and assign a large integer 𝐼 > | 𝑉 1 | to each of these edges.
As noted before, there is a one-to-one correspondence between matchings of G and (s, t)-flows
in this network, and the value of the flow equals the number of edges in the matching.
Since we are assuming that there is no matching which saturates V1, it follows that every flow
has value less than | 𝑉1 | and hence by Max-Flow-Mincut theorem, there exists an (𝑠, 𝑡) −cut
{𝑆, 𝑇} {𝑠 ∈ 𝑆, 𝑡 ∈ 𝑇). Whose capacity is less than | V1 |.
Now every original edge of G has been given a weight larger than | V1 |. Since the capacity of
our cut is less than | 𝑉1 |, no edge of G can join a vertex of S to a vertex of T. Letting 𝑋 =
𝑉 1∩ 𝑆, we have 𝐴(𝑋) ⊆ 𝑆.
Since each vertex in 𝐴(𝑋) is joined to t ∈ T, each such vertex contributes 1 to the capacity of
the cut. Similarly, since s is joined to each vertex in V1\X, each such vertex contributes 1. Since
| 𝑋 | ≤ | 𝐴(𝑋) |, we have a contradiction to the fact that the capacity is less than | 𝑉1 |

Problem 1. Let G be a bipartite graph with bipartition sets 𝑣1, 𝑣2 in which every vertex has the
same degree k. Show that G has a matching which saturates v1.
Solution. Let 𝑋 be any subset of 𝑣1 and let 𝐴(𝑋) be as defined earlier. We count the number
of edges joining vertices of 𝑋 to vertices of 𝐴(𝑋).
On the one hand (thinking of 𝑋), this number is k | X |.
On the other hand (thinking of 𝐴(𝑋)), this number is at most 𝑘 | 𝐴(𝑋) | since 𝑘 | 𝐴(𝑋) | is the
total degree of all vertices in 𝐴(𝑋)).
Hence, 𝑘 | 𝑋 | ≤ 𝑘 | 𝐴(𝑋) |, so | 𝑋 | ≤ | 𝐴(𝑋) |.

Problem 2. Can you conclude from this problem that 𝐺 also has a matching which saturates
𝑉 2? More generally, does 𝐺 have a matching which saturates both 𝑉 1 and 𝑉 2 at the same time
(a perfect matching)?

Solution. Yes, the same argument works. But more easily, note that since 𝐺 is bipartite, the
sum of the degrees of vertices in 𝑉 1 must equal the sum of degrees of vertices in 𝑉 2. Since all
vertices have some degree, we conclude that | 𝑉 1 | = | 𝑉 2 |, so a matching which saturates 𝑉 1

Page 101
must automatically saturate 𝑉 2 as well and vice versa.

11.4.2 Max Flow Min Cut Theorem:

A graph can be thought of as a flow network, where one vertex is specified to be the source
of the flow and another is specified to be the receiver of the flow. As an amount of material
flows from source to receiver, it passes through other inter- mediate vertices, each of which
has a particular flow capacity. The total flow of a network is the amount of material that is
able to make it from source to receiver. A cut in a network is a set of intermediate vertices
whose removal completely cuts the flow from the source to the receiver. The capacity of the
cut is simply the sum of the capacities of the vertices in the cut.

11.4.3. Hall’s Theorem and SDRs:

In this section we consider several classic results concerning matchings. We begin with few
more definitions.
Given a graph G and a matching M, an M-alternating path is a path in G where the edges
alternate between M -edges and non-M -edges. An M-augmenting path is an M -alternating
path where both end vertices are M -unsaturated.
As an example, consider the graph G and the matching M indicated in Figure 11.4.1. An
example of an M -alternating path is {c, a, d, e, i.} An example of an M -augmenting path
is {j, g, f , a, c, b.} The reason for calling such a path “M - augmenting” will become
apparent soon. b c a d e

Figure 11.4.1 The graph G and matching M

Theorem [Link] (Berge’s Theorem) Let M be a matching in a graph G. M is maximum
if and only if G contains no M-augmenting paths.

Proof. First, assume that M is a maximum matching, and suppose that P : {v1, v 2 ,...,
vk } is an M -augmenting path. Due to the alternating nature of M - augmenting paths, it
must be that k is even and that the edges {v2v3, v4, v5, ... , vk−2, vk−1}are all edges of M .
We also see that the edges {v1, v2, v3, v4, ... , vk−1, vk}are not edges of M (Figure 11.4.2.)

But then if we define the set of edges M1 to be M1 = (M \ {v 2, v 3 ,..., vk−2, vk−1}) ∪ {v 1,

Page 102
v 2 ,..., vk−1, vk},

Figure 11.4.2. An M -augmenting path.

then M1 is a matching that contains one more edge than M , a matching that we assumed to
be maximum. This is a contradiction, and we can conclude that G contains no M -
augmenting paths.
For the converse, assume that G has no M -augmenting paths, and suppose that M ′ is a
matching that is larger than M . Define a subgraph H of G as follows: Let V (H) = V (G)
and let E(H) be the set of edges of G that appear in exactly one of M and M ′. Now
consider some properties of this subgraph H. Since each of the vertices of G lies on at most
one edge from M and at most one edge from M ′, it must be that the degree (in H) of each
vertex of H is at most 2. This implies that each connected component of H is either a
single vertex, a path, or a cycle. If a component is a cycle, then it must be an even cycle,
since the edges alternate between M -edges and M ′-edges. So, since M ′ > M, there must
be at least one component of H that is a path that begins and ends with edges from M ′. But
this path is an M -augmenting path, contradicting our assumption. Therefore, no such
matching M ′ can exist—implying that M is maximum.

Before we see Hall’s classic matching theorem, we need to define one more term. If G
is a bipartite graph with partite sets X and Y, we say that X can be matched into Y if
there exists a matching in G that saturates the vertices of X.
Consider the two examples in Figure 11.4.3. In the bipartite graph on the left,

X Y X Y

Figure 11.4.3.

we see that X can be matched into Y. In the graph on the right, though, it is impossible to match
X into Y (why is this?). What conditions on a bipartite graph must exist if we want to match

Page 103
one partite set into the other? The answer to this question is found in the following result of
Hall (Philip, not Monty).
Recall that the neighborhood of a set of vertices S, denoted by N (S), is the union of the
neighborhoods of the vertices of S.

NOTE: The students can either refer 11.4.1. Hall’s Marriage Theorem OR Theorem
[Link] (Hall’s Theorem). Because Hall’s Theorem is often referred to as Hall’s
Marriage Theorem.

Theorem [Link] (Hall’s Theorem). Let G be a bipartite graph with partite sets X and Y
. X can be matched into Y if and only if |N (S)| ≥ |S| for all subsets S of X.

Proof. First suppose that X can be matched into Y, and let S be some subset of X. Since S
itself is also matched into Y , we see immediately that |S| ≤ |N (S)| (see Figure 11.4.4).
Now suppose that |N (S)| ≥ |S| for all subsets S of X, and

N(S)
X Y

Figure 11.4.4
let M be a maximum matching. Suppose that u X is not saturated by M (see Figure11.4.5.)
Define the set A to be the set of vertices of G that can be joined to u.

X Y
Figure 11.4.5

Page 104
By an M –alternating path. Let S =A ∩ X and Let T =A ∩ Y (see Figure 11.4.6). Notice
now that Berge’s Theorem implies that every vertex of T is saturated by

X Y Figure 11.4.6

M and that u is the only unsaturated vertex of S. That is, every vertex of T is saturated,
and every vertex of S u is saturated. This implies that T = S

1. It follows from Berge’s Theorem and the definition of T that N (S) = T. But then we have
that N (S) = S, 1 < S , and this is a contradiction. We conclude that such a vertex u
cannot exist in X and that M saturates all of X.

Given some family of sets X, a system of distinct representatives, or SDR, for the sets in X
can be thought of as a “representative” collection of distinct elements from the sets of X. For
instance, let S1, S2, S3, S4, and S5 be defined as follows:

S1 = {2, 8},
S2 = {8},
S3 = {5, 7},
S4 = {2, 4, 8},
S5 = {2, 4}.

The family X1 = {S1, S2, S3, S4} does have an SDR, namely {2, 8, 7, 4}. The family
X2 = {S1, S2, S4, S5} does not have an SDR.

So under what conditions will a finite family of sets have an SDR? We answer this
question with the following theorem.

Theorem [Link] Let S1, S2, ..., Sk be a collection of finite, nonempty sets. This collection
has an SDR if and only if for every 𝑡𝜖 {1, . . . , 𝑘} the union of any t of these sets contains
at least t elements.
Proof. Since each of the sets is finite, then of course is finite. Let us say that the
elements of S are a1, ..., an.

Page 105
 We now construct a bipartite graph with partite sets X = {S 1 ,... , Sk} and Y =
{a1 , . . . , an } (Figure 11.4.7). We place an edge between Si and aj if and only if aj ∈
Si .

X S1 Sk

Y
a1

Figure 11.4.7 Constructing a bipartite graph

Hall’s Theorem now implies that X can be matched into Y if and only if |𝐴| ≤ |𝑁(𝐴)| for all
subsets A of X. In other words, the collection of sets has an SDR if and only if for every t 𝜖
{1,... ,k} the union of any t of these sets contains at least t elements.

Hall’s Theorem is often referred to as Hall’s Marriage Theorem.

11.5. Summary:
A graph 𝐺 is n-connected if к (𝐺) ≥ 𝑛 and n-edge-connected if 𝜆(𝐺) ≥ 𝑛. We note that
a nontrivial graph is 1-connected if and only if it is connected, and that it is 2-connected if
and only if it is a blockhaving more than one edge. So 𝐾 2 is the only block not 2-connected.

Menger showed that the connectivity of a graph is related to the number of disjoint paths
joining distinct vertices in the graph. In its best-known version, Menger's theorem states that
the maximum number of pairwise internally disjoint paths between a given pair of non-
adjacent vertices in a graph equals the minimum number of vertices whose deletion
disconnects the pair.

Some conditions that imply the existence of Hamiltonian cycles are known though. A
rather obvious intuition is that if a graph is sufficiently dense then it should have long
cycles. The Dirac’s Theorem proves that this intuition is indeed right.

We prove in Hall’s theorem that,

11.6. Keywords: Menger’s Theorem, Dirac’s Theorem, Hall’s theorem.

11.7. Exercises

1. For the graphs of Figure 1.114, with matchings M as shaded, find

Page 106
 (a) an M -alternating path that is not M –augmenting.

(b) an M -augmenting path if one exists; and, if so, use it to obtain a bigger matching.

Figure 11.5.1

2. For each of the following families of sets, determine whether the condition of
Theorem [Link] is met. If so, then find an SDR. If not, then show how the condition
is violated.

(a) {1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5}, {1, 2, 5}
(b) {1, 2, 4}, {2, 4}, {2, 3}, {1, 2, 3}
(c) {1, 2}, {2, 3}, {1, 2, 3}, {2, 3, 4}, {1, 3}, {3, 4}
(d) {1, 2, 5}, {1, 5}, {1, 2}, {2, 5}
(e) {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2, 3, 4}, {2, 3, 4}

3. Let G be a bipartite graph. Show that G has a matching of size at least

|E(G)|/Δ(G).

4. Let Θ = {S1, S 2 ,..., Sr} be a family of distinct nonempty subsets of the

set{1,2,..,,n.} if the S are all of same cardinality, then prove that there exists an
SDR of 𝜃.

5. Let M1 and M2 be matchings in a bipartite graph G with partite sets X and Y . If S ⊆

X is saturated by M1 and T ⊆ Y is saturated by M2, show that there exists a matching
in G that saturates S ∪ T.

Page 107
 6. Let G be a bipartite graph with partite sets X and Y . Let δX denote the minimum
degree of the vertices in X, and let ΔY denote the maximum degree of the vertices
≥
in Y . Prove that if δX ≥ ΔY , then there exists a matching in G that saturates X.

11.8. References
1. F. Harary, ‘Graph Theory’, Addison-Wesley, 1969

2. G. Chartrand and L. Lisniak, ‘Graphs and Digraphs’, Wordsworth, [Link],

California,1986.

Page 108
 UNIT – 12
EULER AND HAMILTONIAN GRAPHS

Structure:

12.0 Objectives

12.1 Introduction

12.2 Euler Circuits and Euler Trails

12.3 Hamilton Cycles and Hamilton Paths

12.4 Summary

12.5 Keywords

12.6 Exercises

12.7 References

12.0 Objectives

The objective of this unit is to make the learners conversant on –

 Euler graph and their Characterization

 Hamilton Graphs and their Properties

12.1 Introduction

The Konigsberg bridge problem is perhaps the best-known example in graph theory. It was a long-
standing problem until solved by Leonhard Euler (1707-1783) in 1736, by means of a graph. Euler
wrote the first paper ever in graph theory and thus became the originator of the theory of graphs as well
as of the rest of topology. The problem is depicted in Fig. 12.1.1.(A). Two islands, С and D, formed
by the Pregel River in Konigsberg were connected to each other and to the banks A and В with seven

Page 109
 bridges, as shown in Fig. 12.1.1(A). The problem was to start at any of the four land areas of the city,
А, В, С or D, walk over each of the seven bridges exactly once, and return to the starting point (without
swimming across the river, of course). Euler represented this situation by means of a graph, as shown
in Fig. 12.1.1(B). The vertices represent the land areas and the edges represent the bridges. As we shall
see in this unit, Euler proved that a solution for this problem does not exist.

Fig. 12.1.1(A). Fig. 12.1.1(B).

The other milestone is due to Sir W. R. Hamilton (1805-1865). In the year 1859 he invented a puzzle
and sold it for 25 guineas to a game manufacturer in Dublin. The puzzle consisted of a wooden, regular
dodecahedron (a polyhedron with 12 faces and 20 corners, each face being a regular pentagon and three
edges meeting at each corner; see Fig. 12.1.2.). The corners were marked with the names of 20 important
cities: London, New York, Delhi, Paris, and so on. The object in the puzzle was to finda route along
the edges of the dodecahedron, passing through each of the 20 cities exactly. Although the solution of
this specific problem is easy to obtain (as we shall see in this unit), to date no one has found a necessary
and sufficient condition for the existence of such a route (called Hamiltoniancycle) in an arbitrary
graph.

Figure. 12.1.2.

Page 110
More over very famous problems such as Chinese Postman problem and Salesman problems can be
solved by determining Euler circuits/ Hamiltonian cycles. In this unit two characterizations of Euler
graphs are presented. Hamiltonian graphs are studied next and some necessary conditions and some
sufficient conditions for graphs to be Hamiltonian are given. However, it still remains a challenging
unsolved problem to discover an elegant, useful characterization of Hamiltonian graphs, rather
than only a disguised paraphrase of the definition.

12.2 Euler Circuits and Euler Trails

Consider a connected graph G. If there is a circuit in G that contains all the edges of G, then that circuit
is called an Euler circuit (or Eulerian line, or Euler tour) in G. If there is a trail in G that contains all
the edges of G, then that trail is called an Euler trail (or Unicursal line) in G.
A connected graph that contains a Euler circuit is called an Euler graph (or Eulerian graph). A
connected graph that contains an Euler trail is called a semi- Euler graph (or Semi - Eulerian graph or
Unicursal graph)
Examples:

G1: G2: G3:

In the above example G1 is an Euler Graph, but G2 and G3 are not Euler graphs.

Theorem 12.2.1: A connected graph G has an Euler circuit (that is, G is an Euler graph) if and only if
all vertices of G are of even degree.

Proof: Let a connected G has an Euler circuit. Then while tracing this circuit we observe every time
the circuit meets a vertex v it goes through two distinct edges incident on v. (one to enter and the other
to exit) This is true for all vertices that belong to the circuit. Since the circuit contains all edges,it meets
all the vertices at least once. Hence degree of every vertex in G is even.

Conversely, suppose that all the vertices of G are of even degree, then we have to prove G has an
Euler circuit.

To prove G has Euler circuit, we give a procedure to construct the circuit.

We construct a circuit starting at an arbitrary vertex v and going through the edges of G such that no
edge is traced more than once. Since every vertex is of even degree, we can depart from every vertex
we enter, and the tracing cannot stop at any vertex other than v. Say this circuit as Q, which starts and

Page 111
 ends with v. If this circuit contains all the edges in G, then the circuit is an Euler circuit.

If not, let us consider the subgraph H obtained by removing all edges that belong to Q from G. The
degrees of vertices in this sub graph are also even. Since G is connected, the circuit Q and the subgraph
H must have at least one vertex, say u, in common. Starting from u, we can construct a circuit Q' in H
as done in G.

The two circuits Q and Q’ together constitute a circuit which starts and ends at the vertex v and has
more edges than Q. If this circuit contains all the edges in G, then the circuit is an Euler circuit.

Otherwise, we repeat the process until we get a circuit that starts from v and ends at v and which
contains all edges in G. (The process ends with an Euler circuit, because G has finite number of edges)
Hence the proof.

Theorem 12.2.2: A connected graph G has an Euler circuit (that is, G is an Euler graph) if and only if

G can be decomposed into edge-disjoint cycles.

Proof: First, suppose that G can be decomposed (partitioned) into edge-disjoint cycles. Since the
degree of every vertex in-a cycle is two, it follows that every vertex in G is of even degree. Therefore,
by the last theorem, G has an Euler circuit.

Conversely, suppose G has an Euler circuit. Then, by the last theorem, every vertex in G is of even
degree. By starting from an arbitrary vertex v in G we can find a cycle C1 in G which starts and ends
with v. Let us remove C1 from G, then all vertices in the resulting graph must also be of even degree,

and in this graph we can construct a cycle C2 as done in G. Remove this cycle C2 and proceed as
above. The process ends when no edges are left in G.

In this process we get cycles C1, C2, … such that whose union is G and intersection is a null graph.
Thus the cycles C1, C2 … form decomposition of G. Hence the proof.

Page 112
Theorem 12.2.3: In a connected graph G with exactly 2k odd vertices, there exist k edge-disjoint
subgraphs such that they together contain all edges of G and that each is a unicursal graph.

Proof: Let the odd vertices of the given graph G be named 𝑣1 , 𝑣2 , … , 𝑣𝑘 ; 𝑤1 , 𝑤2 , … , 𝑤𝑘 in any
arbitrary order. Add k edges to G between the vertex pairs (𝑣1 , 𝑤1 ), (𝑣2 , 𝑤2 ), … , (𝑣𝑘 , 𝑤𝑘 ) to form a
new graph 𝐺 ′ .
Since every vertex of 𝐺 ′ is of even degree, 𝐺 ′ consists of an Euler line ρ. Now if we remove from ρ
the k edges we just added (no two of these edges are incident on the same vertex), ρ will be split into
к walks, each of which is a unicursal line; the first removal will leave a single unicursal line; the second
removal will split that into two unicursal lines; and each successive removal will split a unicursal line
into two unicursal lines, until there are к of them. Thus the theorem.

Arbitrarily Traversable Graphs: A graph is arbitrarily traversable from a vertex v0 if the

following procedure always results in an Eulerian trail: Start at vertex v0 by traversing any incident
edge; on arriving at a vertex u depart by traversing any incident edge not yet used, and continue until
no new edges remain.

¤ An Eulerian graph is arbitrarily traversable from v0 if and only if every cycle contains v0.

¤ If G is arbitrarily traversable from v0, then v0 has maximum degree.

¤ If G is arbitrarily traversable from v0, then either v0 is the only cut vertex or G has no cut vertices.

Arbitrarily traversable graphs is one of the very attractive research topic in graph theory, for the
characterization and advanced studies on this topic one can refer the books entitled

12.3 Hamilton Cycles and Hamilton Paths

Let G be a connected graph. If there is a cycle in G that contains all the vertices of G, then that cycle
is called a Hamilton cycle in G. Let G be a connected graph. If there is a path in G that contains all the
vertices of G, then that cycle is called a Hamilton path in G.

Page 113
A graph that contains a Hamilton cycle is called a Hamilton graph (or Hamiltonian graph).

Examples:

G1: G2: G3:

In the above example G1 and G3 are Hamilton graphs, but G2 is not a Hamilton graph.

Note: In considering the existence of a Hamiltonian cycle (or path), we need only consider simple
graphs. This is because a Hamiltonian cycle (or path) traverses every vertex exactly once. Hence it
cannot include a self-loop or a set of parallel edges. Thus a general graph may be made simple by
removing parallel edges and self-loops before looking for a Hamiltonian cycle in it. Thus in this section
we restrict we restrict our attention to simple graphs

The graphical representation of the Figure 12.1.2. is shown below and it is a Hamiltonian Graph.
(Hamiltonian cycle is shown in dark edges)

The following graphs are not Hamiltonian (prove !)

Although there is no easy testable characterization known for Hamiltonian cycles/paths, we study

Page 114
necessary conditions and sufficient conditions. Note that it is still remains a challenging unsolved
problem to discover an elegant, useful characterization of Hamiltonian graphs.

Theorem 12.3.1: If G has a Hamiltonian cycle, then for each non-empty set S V (G), the graph

G – S has at most |S| components.

Proof: Let the graph G has a Hamiltonian cycle and S  V (G) be a non empty set. While tracing the
Hamiltonian cycle, a movement shall begin from one vertex to another. In that process its journey may
starts either from a vertex of S or G – S. When it leaves a component of G – S it must land only in S
and every time it will land in a distinct vertex of S.

¤ The above theorem gives a necessary condition and this condition guarantees that G is 2-
connected (deleting one vertex do not disconnect the graph), but the condition is not sufficient
(i.e. it does not guarantee a Hamiltonian cycle).
Sufficient Conditions: The number of edges needed to force a graph on n vertices to be
Hamiltonian is quite large (think!). A simplest sufficient condition is a lower bound on the
minimum degree; it is given by the following theorem.

Lemma 12.3.2 (Ore’s Theorem): Let G be a simple connected graph with n vertices, where n ≥ 3.
If the sum of degrees of every pair of non-adjacent vertices is greater than or equal to n, then G is
Hamilton.

Proof of the lemma is included in the proof of following theorem

Page 115
Theorem 12.3.3: (Dirac [1952]). Let G be a simple connected graph with n vertices, with n ≥ 3. If the

degree of every vertex is greater than or equal to n/2, then G is Hamilton. (Or If G is a simple (p, q)
𝑝
graph with at least three vertices and 𝛿(𝐺) ≥ then G is Hamiltonian.)
2

Proof: The condition n ≥ 3 is annoying but must be included, since K2 is not Hamiltonian but has two vertices
2
and satisfies 𝛿 (K2 ) =2 = 1.

The proof uses contradiction and extremality. If there is a non–Hamiltonian graph satisfying the
hypotheses, then adding edges cannot reduce the minimum degree. Thus we may restrict our
𝑛
attention to maximal non–Hamiltonian graphs with minimum degree at least 2 , where “maximal”
means that adding any edge joining nonadjacent vertices creates a spanning cycle (i.e. a Hamiltonian
cycle).
Let u and v are non-adjacent in G. Then the maximality of G implies that G + uv has a spanning
Cycle, hence G has a spanning path 𝑢 = 𝑣1 , 𝑣2 , … , 𝑣𝑛 = 𝑣. To prove the theorem it suffices to make a
small change in the spanning cycle of 𝐺 + 𝑢𝑣 to avoid using the edge 𝑢𝑣; this will build a spanning
cycle in 𝐺. Let S = {i : u adjacent to vi+1} and T = {i : v adjacent to vi}. Then by the principle of
inclusion/exclusion, we have;
|S  T| = |S| + |T| – |S ∩ T|  deg (u) + deg (u) = |S| + |T| = |S  T| + |S ∩ T| ≥ n.
Neither S nor T contains the index n. Thus |S ∩ T| ≥ 1. Therefore, there exist index i (2  i  n – 1),
such that u adjacent to vi+1 and v is adjacent to vi, then u  v1, vi1, vi2 , … , vn , vi, vi1, vi2 , … , v2,

v1u is a spanning cycle. (Shown in the following figure).

We have established a contradiction by finding a spanning cycle in G. Hence there is no (maximal

non-Hamiltonian graph satisfying the hypothesis. This completes the proof.

u  v1 v2 v3 vi vi1 vn1 vn  v

Page 116
Corollary 12.3.4:. (Ore [1960]) Let G be a simple graph. If 𝑢, 𝑣 are distinct non adjacent vertices of 𝐺

with 𝑑(𝑢) + 𝑑(𝑣) ≥ 𝑛(𝐺), then G is Hamiltonian if and only if 𝐺 + 𝑢𝑣 is Hamiltonian.

Number of Hamiltonian Cycle in a Graph: A given graph may contain more than one Hamiltonian
cycle. Of interest are all the edge-disjoint Hamiltonian cycles in a graph. The determination of the exact
number of edge-disjoint Hamiltonian cycles (or paths) in a graph in general is also an unsolved

problem. However, the number of edge-disjoint Hamiltonian cycles in a complete graph with odd
number of vertices is given by the following theorem.

Theorem 12.3.5: In the complete graph with n vertices, where n is an odd number ≥ 3. There are
𝑛−1
edge-disjoint Hamiltonian cycles.
2

Proof: Let G be a complete graph with n vertices, where n is odd and ≥ 3. Denote the vertices of G
by 1, 2, 3 . . . 𝑛 and represent them as equispaced points on the circle as shown in the following Figure

We note that the polygonal pattern of edges from vertex 1 to vertex n form a cycle in G that includes all
the vertices of G. Therefore, this cycle is a Hamilton cycle and call this by C1. (Note in G any two

pair of vertices is adjacent) Now, rotate the polygonal pattern clockwise by

360
degree, we get
𝑛−1

Page 117
Again it forms a cycle in G that includes all the vertices of G. This cycle is therefore a Hamilton
cycle and call this by C2. And we observe every edge in first cycle and second cycles are different.
360 𝑛−1
Continuing the process, for each rotation of degree we get new cycles. After rotations the
𝑛−1 2
𝑛−1
patterns start repeating. Thus G has edge disjoint Hamilton cycles. This completes the proof.
2

NOTE:
𝑛(𝑛−1)
 A complete graph G of n vertices has edges, and a Hamiltonian cycle in G consists of n
2
𝑛−1
edges. Therefore, the number of edge-disjoint Hamiltonian cycles in G cannot exceed .
2

 The above theorem can be stated in other form as follows: “If n is odd and n ≥ 3, then Kn can be
𝑛−1
decomposed in to edge disjoint Hamilton cycles”.
2

Seating Problem: Nine members of a new club meet each day for lunch at a round table. They decide
to sit such that every member has different neighbors at each lunch. How many days can this
arrangement last?

Solution: This situation can be represented by a graph with nine vertices such that each vertex
represents a member, and an edge joining two vertices represents the relationship of sitting next to each
other.

Representing a member x by a vertex and the possibility of his sitting next to another member у by an
edge between x and y, we construct a graph G. Since every member is allowed to sit next to any other
member, G is a complete graph of nine vertices (nine being the number of people to be seated around
the table). Every seating arrangement around the table is clearly a Hamiltonian cycle.

The first day of their meeting they can sit in any order, and it will be a Hamiltonian cycle H 1. The
second day, if they are to sit such that every member must have different neighbors, we have to find
another Hamiltonian cycle H2 in G, with an entirely different set of edges from those in H1; that is, H1
and H2 are edge disjoint Hamiltonian cycles. From Theorem 12.3.5 the number of edge-disjoint
Hamiltonian cycles in G is four; therefore, only four such arrangements exist among nine people.

Page 118
Travelling Salesman Problem: A problem closely related to the question of Hamiltonian cycles is the
traveling-salesman problem, stated as follows: A salesman is required to visit a number of cities during
a trip. Given the distances between the cities, in what order should he travel so as to visit every city
precisely once and return home, with the minimum mileage traveled?

Representing the cities by vertices and the roads between them by edges, we get a graph. In this graph,
with every edge ei there is associated a real number (the distance in miles, say), w (ei). Such a graph is
called a weighted graph; w (ei) being the weight of edge ei. In this problem, if each of the cities has a
road to every other city, we have a complete weighted graph. This graph has numerous Hamiltonian
cycles, and we are to pick the one that has the smallest sum of distances (or weights).

The total number of different (not edge disjoint, of course) Hamiltonian cycles in a complete graph of
(𝑛−1)!
n vertices can be shown to be . This follows from the fact that starting from any vertex we
2

have n – 1 edges to choose from the first vertex, n – 2 from the second, n – 3 from the third, and so on.
These being independent choices, we get total number of possible choices is (n – l)!. This numberis,
however, divided by 2, because each Hamiltonian cycle has been counted twice (Think; how each
Hamiltonian cycle has been counted twice?).

Theoretically, the problem of the traveling salesman can always be solved by enumerating all
(𝑛−1)!
Hamiltonian cycles, calculating the distance traveled in each, and then picking the shortest one.
2

However, for a large value of n, the labor involved is too great even for a digital computer. The problem
is to prescribe a manageable algorithm for finding the shortest route. No efficient algorithm for
problems of arbitrary size has yet been found, although many attempts have been made.

12.4. Summary:

In a connected graph G a circuit that contains all the edges of G is called an Euler circuit and the graph
that contains an Euler circuit is called an Euler graph. Two well-designed characterization of Euler
graphs are

i) A connected graph G is an Euler graph if and only if all vertices of G are of even degree.

ii) A connected graph G is an Euler graph if and only if G can be decomposed into edge-disjoint
cycles.

Page 119
In a connected graph G a cycle that contains all the vertices of G, is called a Hamilton cycle and the
graph that contains a Hamilton cycle is called a Hamilton graph (or Hamiltonian graph). It still
remains a challenging unsolved problem to discover characterizations of Hamiltonian graphs.
Theorems by Ore and Dirac provide only sufficient conditions for the graph to be Hamiltonian.

12.5. Key words:

Euler graph, Euler line, Euler circuit, Hamiltonian graph, Hamiltonian cycle

12.6. Exercise:
1. For which values of integers m and n, the graph 𝐾𝑚,𝑛 is Euulerian?
2. For a connected graph G, prove that following are equivalent.

i) G is Eulerian.

ii) Every vertex in G is of even degree

iii) G can be decomposed into edge disjoint cycle

3. Show that a connected graph with exactly two vertices of odd degree has an Euler trail.

4. Let G be a simple graph of order n, (n ≥ 3) with m edges. If m ≥ ½ (n – 1) (n – 2) + 2, prove

thatG is Hamilton. Is the converse true?

5. How many edge disjoint Hamilton cycle exist in complete graph with seven vertices? Also draw
the graph to show these cycles.

6. Prove that, if G is a bipartite graph with an odd number of vertices, then G is non-Hamiltonian.

7. Which of the following graphs are Euler graphs and which of them are Hamiltonian? Justify your
answer

Page 120
8. Show that for n ≥ 2 the number of Hamiltonian cycles in the complete bipartite graph 𝐾𝑛,𝑛
1
is 2 (𝑛 − 1)! 𝑛!.

12.7. References:

1. F. Harary, ‘Graph Theory’, Addison-Wesley, 1969

2. Narsingh Deo, ‘Graph Theory with Applications to Engineering and Computer

Science’,PHI, 2011.
3. D.B. West, ‘Introduction to Graph theory’, Prentice Hall India 2001

4. G. Chartrand and L. Lisniak, ‘Graphs and Digraphs’, Wordsworth, [Link],

California, 1986.

Page 121
 BLOCK – IV

PLANARITY AND COLORABILITY

Page 122
 UNIT – 13
PLANAR GRAPHS

Structure:
13.0. Objectives

13.1 Introduction

13.2 Planar graphs

13.3 Detection of Planarity

13.4 Geometric Dual

13.5 Crossing Number and Thickness

13.6 Summary

13.7 Keywords

13.8 Exercises

13.9 References

Page 123
13.0. Objectives
The objective of this unit is to make the learners conversant on –
 Planar and Non planar graphs and Euler’s theorem and applications
 Detection of Planarity and Kuratowski's theorem
 Geometric Dual
 Crossing Number and Thickness

13.1. Introduction
In Previous blocks we studied properties of subgraphs, such as paths, circuits, spanning trees, and
cut-sets, in a given connected graph G. In this chapter we shall subject the entire graph G to the
following important question: “Is it possible to draw G in a plane without its edges crossing over?”

This question of planarity is of great significance from a theoretical point of view. In addition,
planarity and other related concepts are useful in many practical situations. For instance, in the design
of a printed-circuit board, the electrical engineer must know if he can make the required connections
without an extra layer of insulation. The following is one of the famous puzzles in 17th century.

Utilities Problem: There are three houses (Figure 13.1.1) H1, H2, and H3, each to be connected to
each of the three utilities water (W), gas (G), and electricity (E) by means of conduits. Is it possible
to make such connections without any crossovers of the conduits?

Figure 13.1.2 shows how this problem can be represented by a graph the conduits are shown as edges
while the houses and utility supply centers are vertices. As we shall see in this unit that the graph in
Fig. 13.1.2 cannot be drawn in the plane without edges crossing over. Thus the answer to the problem
is no.

Figure 13.1.1

Page 124
 Figure 13.1.2

A natural question now is: How can we tell if a graph G [which may be given by an abstract notation
G = (V, Ε) or by one of its geometric representations] is planar or nonplanar? To answer this
question, we discuss two specific nonplanar graphs which are of fundamental importance. These
graphs are called Kuratowski's graphs, after the Polish mathematician Kasimir Kuratowski, who
discovered the unique property of planar graphs.

13.2. Planar graphs

A graph G is said to be planar if there exists some geometric representation of G which can be drawn
on a plane such that no two of its edges intersect. A graph that cannot be drawn on a plane without a
crossover between its edges is called non-planar. A drawing of a geometric representation of a graph
on any surface such that no edges intersect is called embedding (or planar embedding).

An embedding of a planar graph G on a plane is called a plane representation of G (or plane

representation of G).
Examples:
a a
i. d e
e ii
b d b
f f
c c

Figure 13.2.1

Page 125
 i) The geometric representation shown in above (i) is not embedded in a plane, because the
edges e and f are intersecting. But if we redraw edge f outside the quadrilateral, leaving the
other edges unchanged, we have embedded the new geometric graph (ii) in the plane, thus
showing that the graph which is being represented by is planar.

ii) The two isomorphic graphs given below are different two different geometric representations
of the graph Q3. One of the diagrams is a planar representation Q3 the other one is not.

Figure 13.2.2

Theorem 13.2.1: The complete graph of 5 vertices is non-planar. (Or K5 is non-planar).

Proof: Let the 5 vertices in the complete graph K5 be named as v1, v2, v3, v4 and v5. A complete graph
is a simple graph in which every vertex is joined to every other vertex by an edge. We must have a
circuit connecting from v1 to v2 to v3 to v4 to v5 to v1 that is a pentagon. This pentagon must divide the
plane into two regions, one inside pentagonal and the other outside. Now vertex v1 is to be connected
to v3 by an edge either inside or outside the pentagon (without intersecting the five edges drawn
v2 v2
previously v2

v1 v3 v1 v3 v1 v3

v5 v5 v4 v5 v4
v4
v2
v2
v1 v3
v1 v3

v5 v4
v5 v4

Figure 13.2.3

Page 126
Suppose that we choose to draw a line from v1 to v3 inside the pentagon. Now we have to draw an edge
from v2 to v4 and another one from v2 to v5. Since neither of these edges can be drawn inside the
pentagon without crossing over the edge already drawn, we draw both these edges outside the
pentagon. The edge connecting v3 and v5 cannot be drawn outside the pentagon without crossing the
edge between v2 and v4. Therefore, v3 and v5 have to be connected with an edge inside the pentagon.
Now we have yet to draw an edge between v1 and v4. This edge cannot be placed inside or outside the
pentagon without a crossover. Thus the graph cannot be embedded in a plane.

Theorem 13.2.2: Complete bipartite graph K3,3 is non-planar.

Proof: Let K3,3 has 6 vertices and 9 edges and is regular graph. Let 6 vertices in K3,3 be labelled as v1,
v2, v3, v4, v5 and v6. Since K3,3 is regular all the vertices are of the same degree and hence there exista
circuit v1 → v2 → v3 → v4 → v5 → v6 → v1 which is hexagon.

Figure 13.2.4

Now we connect the vertices v1 and v4 by an edge inside or outside the hexagon without crossover of
edges. Let us connect v1 and v4 by an edge inside the hexagon. Then we can connect v2 to v5 by an
edge outside the hexagon without any intersection. But an edge between v3 and v6 cannot be drawn
inside or outside the hexagon without any intersection. Therefore, K3,3 is non-planar.

Remark:

1. The graph K5 is called Kuratowski's first graph and K3,3 is called Kuratowski's second graph.

2. Both K5 and K3,3 are regular graphs and both are non-planar.

3. The removal of one edge or one vertex makes each graph a planar graph.

Page 127
 4. Kuratowaski’s 1st graph K5 is non-planar graph with smallest number of vertices.

5. Kuratowaski’s 2nd graph K3,3 is non-planar graph with smallest number of edges.

6. Both K5 and K3,3 are the simplest non-planar graphs.

7. A complete graph with 4 vertices is always planar.

Regions: A plane representation of a graph divides the plane into regions (also called windows,
faces, or meshes). A region is characterised by a set of edges (or the vertices) forming its boundary.
Note that a region is not defined in a nonplanar graph or even in a planar graph not embedded in a
plane. For example, the geometric graph in Fig. 13.1.2 does not have regions. Thus a region is a
property of the specific plane representation of a graph and not of an abstract graph per se.

Example:

1 2 6

3 4

Figure 13.2.5

The numbers stand for regions 1, 2, 3, 4 and 5 are interior regions and 6 is exterior region.

Infinite Region: The portion of the plane lying outside a graph embedded in a plane, such as region6
in the above Figure, is infinite in its extent. Such a region is called the infinite, unbounded, outer, or
exterior region for that particular plane representation. Like other regions, the infinite region is also
characterized by a set of edges (or vertices). Clearly, by changing the embedding of a given planar
graph, we can change the infinite region (observe!).

Theorem 13.2.3: A planar graph may be embedded in a plane such that any specified region (i.e.,
specified by the edges forming it) can be made the infinite region.

Proof of the above theorem is left to the reader.

Page 128
Embedding on a Sphere: To eliminate the distinction between finite and infinite regions, a planar
graph is often embedded in the surface of a sphere. It is accomplished by stereographic projection of
a sphere on a plane. Put the sphere on the plane and call the point of contact SP (south pole). At point

SP, draw a straight line perpendicular to the plane, and let the point where this line intersects the
surface of the sphere be called NP (north pole). See figure 13.2.6

Theorem 13.2.4: A graph can be embedded in the surface of a sphere if and only if it can be
embedded in a plane.

Proof: Consider a sphere on a plane with the point of contact SP (South Pole). At this point draw a
straight line perpendicular to the plane. This line will meet the sphere exactly one point called the
North Pole (NP).

Figure 13.2.6

Now corresponding to a any point P in the plane, there exist a unique point P' on the surface of a
sphere and vice versa, where P' is the point of intersection of the line joining NP and P and the
surface of the sphere. Thus there is a one to one correspondence between the points of the sphere and
the finite points on the plane and the points at infinity in the plane corresponds to the point NP on the
sphere. This shows that any graph that can be embedded in a plane can also be embedded in the
surface of a sphere and vice-versa. Hence the proof.

Page 129
Thinking in terms of the regions on the sphere, we see that there is no real difference between the
infinite region and the finite regions on the plane. Therefore, when we talk of the regions in a plane
representation of a graph, we include the infinite region. Also, since there is no essential difference

between an embedding of a planar graph on a plane or on a sphere (a plane may be regarded as the
surface of a sphere of infinitely large radius), the term "plane representation" of a graph is often used
to include spherical as well as planar embedding.

Euler's Formula: Since a planar graph may have different plane representations, we may ask if the
number of regions resulting from each embedding is the same. The answer is yes. Theorem 13.2.4,
known as Euler's formula, gives the number of regions in any planar graph.

Theorem 13.2.5: A connected planar graph with n vertices and e edges has e – n + 2 regions.

Proof: It is sufficient to prove the theorem for a simple graph. Also we remove all the edges which
do not form the boundaries of any region.

In fact, addition (or removal of any such edge) increasing or decreasing both e and n by one keeping
the e – n fixed. Since any simple planar graph can have a planar representation such that edge is a
straight line segment, each region in G is a polygon. Let f be the total number of regions. Among

these we have regions with 3 boundary edges, 4 boundary edges etc. Let there be K3 regions with 3
boundary edges, K4 regions with 4 boundary edges. . . Kr, r sided region where Kr is the number of
regions where r is as large as possible. Since each edge is on the boundary of exactly two regions, we
have

3 K3 + 4 K4 + . . . + r Kr = 2e and K3 + K4 + . . . + Kr = f

Now consider the angle subtended at the vertex by the edges. There will be a total of 2π around each
vertex. The sum of all angles subtended at each vertex in a polygon of n sides in 2πn. The sum of all
interior angles in a P sided polygon is π (P - 2) and the sum of all exterior angles is π (P + 2).

Thus a sum of all the angles subtended at each vertex = (Sum of all interior angles) + (exterior angle
in the infinite region). Therefore,

Page 130
 2πn = π (3 – 2) K3 + π (4 – 2) K4 + . . . + π (r – 2) Kr + 4π

2πn = π (3K3 + 4K4 + . . . + r Kr) – 2π (K3 + K4 + . . . + Kr) + 4π

2πn = π (2 e) – 2π f + 4π

n = e – f +2

f = e – n + 2.

Corollary 13.2.6: In any simple connected planar graph with f regions, n vertices and e edges where
e > 2 the following inequalities must hold e ≥ 3/2 f and e ≤ 3n – 6.

Proof: Since each region is bounded by at least 3 edges and each edge belongs to exactly two
regions, we have; 2e ≥ 3 f  e ≥ 3/2 f

By the Theorem 13.2.5, f = e – n + 2 and also 2 e ≥ 3 f  2 e ≥ 3 (e – n + 2)  e ≤ 3 n – 6 .

Note: Corollary 13.2.6 is often useful in finding out if a graph is nonplanar. For example, in the case
of K5, the complete graph of five vertices n = 5, e = 10, 3n – 6 = 9 < e. Thus the graph violates
inequality in the Corollary 13.2.6 and hence it is not planar. Incidentally, this is an alternative and
independent proof of the non-planarity of Kuratowski's first graph.

The reader must be warned that inequality in the Corollary 13.2.5 is only a necessary, but not a
sufficient, condition for the planarity of a graph. In other words, although every simple planar graph
on n vertices must satisfy e ≤ 3 n – 6, the mere satisfaction of this inequality does not guarantee the
planarity of a graph. For example, Kuratowski's second graph, K3,3, satisfies e ≤ 3n – 6, because
e = 9 and 3n – 6 = 3×6 – 6 = 12 > e. Yet the graph is nonplanar.

To prove the nonplanarity of Kuratowski's second graph, we make use of the additional fact that no
region in this graph can be bounded with fewer than four edges. Hence, if this graph were planar, we
would have 2e ≥ 4 f and substituting for f from Euler's formula, we get 2e ≥ 4 (e – n + 2).
Substituting the values of e and n for K3,3, we get or 2×9 ≥ 4(9 – 6 + 2) or 18 ≥ 20, a contradiction.
Hence the graph cannot be planar.

Page 131
13.3. Detection of Planarity
How to tell if a given graph G is planar or nonplanar is an important problem, and "find out by
drawing it" is obviously not a good answer. We must have some simple and efficient criterion.
Toward that goal, we take the following simplifying steps:

Step 1: Since a disconnected graph is planar if and only if each of its components is planar, we need
consider only one component at a time. Also, a separable graph is planar if and only if each of its
blocks is planar. Therefore, for the given arbitrary graph G, determine the set 𝐺 = { 𝐺1 , 𝐺2 , …, 𝐺𝑘 }.
where each 𝐺𝑖 is a nonseparable block of G. Then we have to test each 𝐺𝑖 for planarity.

Step 2: Since addition or removal of self-loops does not affect planarity, remove all self-loops.

Step 3: Since parallel edges also do not affect planarity, eliminate edges in parallel by removing all
but one edge between every pair of vertices.

Step 4: Elimination of a vertex of degree two by merging two edges in series does not affect
planarity. Therefore, eliminate all vertices of degree two by merging two edges in series.

Note: In a graph, two edges are said to be in series if they have exactly one vertex in common and if
this vertex is of degree two.

Repeated application of steps 3 and 4 will usually reduce a graph drastically.

Let the non-separable connected graph 𝐺𝑖 be reduced to a new graph 𝐻𝑖 after the repeated application of
steps 3 and 4. How will graph 𝐻𝑖 look like? Theorem 13.3.1 has the answer.

Theorem 13.3.1: Let set G {G1, G2, Gk }, where eachGi is a non-separable block of G. remove

all self-loops and repeatedly apply the following steps:

Step A: Eliminate edges in parallel by removing all but one edge between every pair of vertices.

Step B: Eliminate all vertices of degree two by merging two edges in series.
The non-separable connected graph 𝐺𝑖 be reduced to a new graph 𝐻𝑖 and it is one of the following:

1. A single edge (i.e. K2), or 2. A complete graph on four vertices (i.e. K4), or

3. A nonseparable simple graph with n  5 and e  7.

Proof is left as an exercise to the reader.

From the Theorem 13.3.1, all Hi falling in categories 1 or 2 are planar and need not be checked

Page 132
further. From now on, therefore, we need to investigate only simple, connected, nonseparable graphs
of at least five vertices and with every vertex of degree three or more. Next, we can check to see
e  3n  6.
If this inequality is not satisfied, the graph Hi is nonplanar. If the inequality is satisfied,

we have to test the graph further. With this we come to Kuratowski's theorem (Theorem 13.3.2),
perhaps one of the most important results of this unit. Before the theorem we define homeomorphic
graphs.

Homeomorphic graphs: Two graphs G1 and G2 are said to be homeomorphic if one can be obtained
from the other by the creation of edges in series. (i.e. insertion of vertices of degree 2) or the merger
of edge in series.

¤ A graph G is planar if and only if every graph that is homeomorphic to G is planar. (This is a
restatement of series reduction, step 4 in this section.)

Theorem 13.3.2: A graph is planar if and only if it has no subgraph homeomorphic to K5 or K3,3.

Proof: The necessary condition is clear, because a graph G cannot be embedded in a plane if G has a
subgraph that cannot be embedded. That this condition is also sufficient is surprising, and its proof is
tortuous. Several different proofs of the theorem have appeared since Kuratowski stated and proved it
in 1930. For a complete proof of the theorem, the students are suggested to refer the books of Harary.

The example just discussed also points out that although Theorem 13.3.2 (Kuratowski's theorem)
gives an elegant and simple-looking criterion for planarity of a graph, the theorem is difficult to apply
in the actual testing of a large graph. There have been several alternative characterizations of a planar
graph. One of these characterizations, the existence of a dual graph, is the subject of the next
sections.

[Kazimierz Kuratowski was a Polish mathematician and logician. His contributions to mathematics
include - A characterization of Hausdorff spaces which are now called Kuratowski closure axioms;

Page 133
proof of the Kuratowski-Zorn lemma; the characterization of planar graphs now known as
Kuratowski's theorem, etc.]

13.4. Geometric dual:

Consider the plane representation of a graph with 6 regions F1, F2, F3, F4, F5 and F6 as shown in the
Figure 13.4.1 (a). Let us place 6 points P1, P2, P3, P4, P5, P6 one in each region as shown in the
Figure 13.4.1 (b). We join these points according to the following procedure:
1. If two regions Fi and Fj adjacent (i.e. they have a common edge) draw a line joining the points Pi
and Pj such that it intersects the common edge exactly once between Fi and Fj.
2. If there is more than one edge common between Fi and Fj draw one line between Pi and Pj for each
of the common edges.
3. For an edge ek lying entirely in one region Fk draw a self-loop Fk at Pk intersecting ek exactly once.

The procedure is shown in the Figure 13.4.1(c). By this procedure we get a new graph G* consisting
of 6 vertices P1, P2, P3, P4, P5, P6 and of edges joining these vertices such graph G* (as shown in the
Figure 13.4.1 (d)) is called a dual (geometric dual) of G.

P
P

P
(d)
Figure 13.4.1

Page 134
 Properties:
1. There is a one to one correspondence between the edges of the graph G and its dual G*.
2. An edge forming a self-loop in G yields a pendent edge in G*.
3. A pendant edge in G yields a self-loop in G*
4. The edges that are in series in G produce parallel edges in G*.
5. The parallel edges in G produce edges in series in G*.
6. The graph G* can also be embedded in a plane and hence it is planar.
7. G and G* are duals of each other.
8. If n, e, f, r and μ denote the number of vertices, number of edges, number of regions, rank
and nullity of a connected planar graph G and
n*, e*, f *, r* and μ* are corresponding numbers in the dual G* then
n* = f, e* = e, f * = n but then r* = μ and μ* = r

Here we discuss yet another characterization of planar graphs, which is in terms of concept of
duality.

Theorem 13.4.1: A graph has a dual if and only if it is planar.

Proof: If G is planar then G has a dual. We prove only if part for this we shall show that if G is non-
planar then G has no dual.

Let G be non-planar, then according to Kuratowaski’s theorem G may contain K3,3 or K5 or a graph
homeomorphic to these two. It is enough to show that neither k5 nor K3,3 has a dual. If possible let
K3,3 has a dual D we observe that cut-sets in K3,3 corresponds to the circuits in D and vice-versa. In
K3,3 there is no cutest of two edges and hence D has no circuit of length two which means that there
is D has no parallel edges. Also we observe that every circuit in K3,3 is of length 4 or 6 only.
Therefore, D has no cutest with less than 4 edges. Hence the degree of every vertex in D should be at
least 4. This implies that D must contain at least 5 vertices and each of degree at least 4. Therefore, D
must have at least 10 edges but K3,3 has 9 edges, a contradiction to the fact that a graph and its dual
must have same number of edges. Therefore, assumption is wrong. Hence K3,3 cannot have a dual.

Next suppose that K5 has a dual H. We observe that K5 has 10 edges, no pair of parallel edges, no
cutest with 2 edges and has cut-sets with 4 or 2 edges. Therefore, the graph H must contain 10 edges
no vertex of degree less than 3 no pair of parallel edges and circuits if length 4 or 6 only. Hence H
must contain an hexagon (a circuit of length 6) and no more than 3 edges can be added to a hexagon
without creating a circuit of length 3 or a pair of parallel edges. But both these are not allowed in H, a
contradiction.

Page 135
Self-Dual Graphs: If a planar graph G is isomorphic to its own dual, it is called a self-dual graph. It
can be easily shown that the four-vertex complete graph is a self-dual graph. Self-dual graphs have
interesting properties and pose some unsolved problems.

13.5. Thickness of graph

The least number of planar sub graphs whose union is the given G is called the thickness of G.

Example: i) The thickness of a planar graph is one.

ii) Thickness of each of Kuratowski’s graphs is two.

Crossing number: The least number of crossing or intersection required to draw a graph in a plane is
called the crossing number.

Example: i) The crossing number of planar graphs is zero.

ii) The crossing number of Kuratowski’s graphs is one.

13.6. Summary
Can a given graph be placed in a plane without its edges crossing over? This is clearly a geometric
question about the graph an object that exists in two different worlds, purely combinatorial and
purely geometric. Harary states thus, "one of the most fascinating areas of study of graphs is the
interplay between considering a graph as a combinatorial object and as a geometric figure."

On probing a bit further, we discovered that we needed to investigate only simple, nonseparable
graphs which have no vertex of degree less than three. Moreover, we found that any graph with the
number of edges e  3n  6 need not be investigated any further, because such a graph is nonplanar.

For graphs that are nonplanar, additional relevant properties, such as thickness and number of
crossings, were defined and discussed. There are many unsolved problems in this field of study.
Because of the current interest in such areas as automatic wiring of complex systems, technology of
printed circuits, and design of large-scale integrated circuits, these geometrical properties of graphs
are of practical importance. The existence of a dual graph, in addition to being a condition equivalent

to that of planarity, is important in its own right.

13.7. Keywords
Planar graphs, Euler’s Theorem, Kuratowski’s graphs, Geometric dual, Thickness and Crossing
number.

Page 136
13.8. Exercise
1) Show that every planar graph of order n  4 has at least four vertices of degree less than or equal
to 5.

2) Prove that a graph G is planar if and only if each of its blocks is planar.

3) If a ( p1, q1 ) graph and a ( p2 , q2 ) graph are homeomorphic, then prove p1  q2  p2  q1 .

that

4) Show that the complete graph of four vertices is self-dual. Also give one more example of a self-
dual graph.

5) Show that the graphs of Figure is nonplanar. Determine the number of crossings and
thickness of the graph

6) Draw the geometric dual of the graph.

7) Show by sketching that the thickness of the eight-vertex complete graph is two, whereas that
of the nine-vertex complete graph is three.

13.9. References
1. F. Harary, Graph Theory, Addison-Wesley, 1969
2. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science, PHI,
2011.
3. B. Sooryanarayana and G. K. Ranganath, Text book of graph theory, S. Chand and Co. New
Delhi.
4. G. Chartrand and L. Lisniak, Graphs and Digraphs, Wordsworth, [Link], California,
1986.

Page 137
 UNIT – 14
COLORABILITY

Structure:

14.0. Objectives

14.1. Introduction

14.2. Chromatic number

14.3. Four color theorem

14.4. Summary

14.5. Keywords

14.6. References

14.0. Objectives
The objective of this unit is to make the learners conversant on –
Coloring of graphs, Chromatic numbers, Four color theorem

14.1. Introduction
A coloring of a graph G is an assignment of colors to its vertices such that no adjacent vertices have the
same color. If the graph G is colored such that no two adjacent vertices have the same color, then we say
that the graph is properly colored. A coloring of a graph G which consists of k different colors is said to
be k-coloring
In general, a given graph can be properly colored in many different ways. But here we are interested to
find the minimum number of colors, required for proper coloring of a graph.
For example, Fig.14.1.1 shows two different proper colorings of graph with different number of colors.

Page 138
 Fig 14.1.1

14.2. Chromatic Number (Chromatic Index)

The minimum number of colors required for proper coloring of the graph is chromatic number of the
graph or (chromatic index of G) and is denoted by 𝜒(𝐺). A graph G is n-colorable if 𝜒(𝐺) ≤ 𝑛 and is n-
chromatic if 𝜒(𝐺) = 𝑛. Since G obviously has a p-coloring and a 𝜒(𝐺)- coloring, it must also have an n-
coloring whenever 𝜒(𝐺) < 𝑛 < 𝑝.
The chromatic numbers of some of the familiar graphs are easily determined, namely 𝜒(𝐾𝑝 ) =

𝑝, 𝜒(𝐾𝑝 − 𝑥) = 𝑝 − 1, 𝜒 (𝐾𝑝 ) =1, 𝜒 (𝐾𝑚,𝑛 ) = 2, 𝜒(𝐶2𝑛 ) = 2, 𝜒(𝐶2𝑛+1 )=3, and for any nontrivial tree
T, 𝜒 (T)=2.
Obviously, a graph is 1-chromatic if and only if it is totally disconnected. A characterization of
bicolorable (2-colorable) graphs was given by konig.
If the graph is disconnected, then coloring of one component of the disconnected graph does not affect
the coloring of the other components. Therefore, in coloring problems, we assume that graphs are
connected. If a graph has parallel edges, then all parallel edges can be replaced by a single edge without
affecting the adjacency of vertices. Therefore, in coloring problems, we assume that graphs are simple.
From the definition of chromatic number, it is clear that:
1. The chromatic number of a null graph is 1.
2. The chromatic number of a graph having one or more edges is at least two.
3. The chromatic number of complete graph with n vertices is n.
4. The chromatic number of a graph, having a triangle is at least three.
5. If a graph is a circuit with n vertices, then
(i) it is 2-chromatic if n is even.
(ii) it is 3-chromatic if n is odd.
6. The chromatic number of a bipartite graph with non-empty edge-set is two.

Page 139
7. The chromatic of a tree with at least two vertices is 2 as these are connected acyclic graphs.
8. If a graph is a circuit and it is given that the chromatic number of this graph is even, then it has even
number of vertices (edges). If a circuit graph is 3-chromatic, then the number of vertices in a graph is odd.

Example 1. Find the chromatic number of the following graph.

Solution: The vertices 𝑣1 , 𝑣2 and 𝑣3 will have to be assigned different colours as each of these vertices is
adjacent to the other vertices. Let these colors be named as 1, 2 and 3 respectively. The vertex 𝑣4 can be
assigned colour 1. The vertex 𝑣5 can be assigned colour 3. Vertex 𝑣6 can be assigned colour 2 and vertex
𝑣7 can be assigned colour 1 as it is adjacent to 𝑣5 and 𝑣6 , Therefore, three colours are sufficient for
coloring this graph. So the given graph is 3-chromatic as given below:

Example 2 Find the nature of the graph whose chromatic number is 1.

Solution It is possible when there is no edge in the graph. i.e., when the graph is a null graph the
chromatic number will be 1.

Example 3 Show that the regions of a planar graph can be two colored if each vertex is of even degree.
Solution Let G be a graph in which all the vertices are of even degree. So, G is an Euler graph and hence
all cut-sets of G have even number of edges. Thus, all the Circuits in G* (dual of G) are of even length
and hence vertices of G* can be two-colored. Thus, the region of G can be two-colored.

Page 140
Theorem 14.2.1. Every tree with two or more vertices is 2- chromatic but converse is not true.
Proof: Let T be a tree with two or more vertices. Select any vertex v in T. Assign v with color 1, then all
the vertices adjacent to v are assigned color 2. Now color all the vertices adjacent to those vertices which
have been colored with color 2 using color 1. Continue this process until every vertex of T is colored.

Figure 14.2.1
Since there is one and only one path between any two vertices in a tree, no two adjacent vertices will have
the same color. The tree T has at least two vertices. Therefore, it will have at least one edge. Hence, one
color would not be enough. Hence, T is 2-chromatic.
The following example shows that not every 2-chromatic graph is a tree.

Example 4 Give an example of a graph which is two-chromatic but not a tree.

Solution Consider the following graph, which clearly is 2-chromatic. But it is not a tree.

Theorem 14.2.2. A graph with edge 𝑒 ≥ 1 is 2-chromatic if and only if it has no circuits of odd length.
Proof: Suppose that G is a connected graph with circuits of even length. Choose any vertex and color it
with color 1. Next color all the vertices adjacent to it with color 2. If a vertex is colored with color 2, then
any vertex adjacent to vertices colored with color 2 will be colored by color 1. Since every circuit has
even length, no adjacent vertices will have the same color. Hence, G is 2-chromatic.
Conversely, suppose G has a circuit of odd length then we need at least three colors for coloring the
circuit. Hence, chromatic number of G is greater than or equal to 3, which is a contradiction. Hence, the

Page 141
graph G has no circuits of odd length.
Theorem 14.2.3. A graph G with at least one edge is bipartite if and only if G is 2-chromatic.
Proof: Let G be a 2-chromatic graph. Let 𝑣1 be the set of vertices with color 1 and let 𝑣2 be the set of
vertices with color 2. Then 𝑣1 and 𝑣2 make a partition of the vertices of G such that every edge in G joins
a vertex in 𝑣1 with vertex in 𝑣2 .Hence, G is a bipartite graph.
Conversely, let G be a bipartite graph with at least one edge. Let 𝑣1 and 𝑣2 be the partition of the vertex
set of G such that every edge in G joins a vertex in 𝑣1 to a vertex in 𝑣2 . If we assign colour 1 to all
vertices in 𝑣1 and colour 2 to all vertices in 𝑣2 , then G has a proper colouring. Since G has at least one
edge, therefore, two colours are necessary. Hence, G is 2-chromatic.

Theorem 14.2.4. If D is the maximum degree of the vertices in a graph G, then the chromatic number of
G is less than or equal to (D+1).
Proof: Let G be a graph with n vertices. Here we will prove the given result by mathematical induction
on the number of vertices. If G has one or two vertices, then obviously the result is true. We assume that
the result is true for all the graphs having less than n vertices. Delete any vertex 𝑣 and all edges incidence
on v.
Now the resulting graph 𝐺 − 𝑣 with 𝑛 − 1 vertices and maximum degree of any vertex in 𝐺 − 𝑣 is at
most D. Hence by induction method, the chromatic number of 𝐺 − 𝑣 is less than or equal to 𝐷 + 1.
We now add the vertex v and all edges incident on v to 𝐺 – 𝑣. Since, degree of v is D, therefore, at most D
colors are required to color all vertices adjacent to v. We can assign a different color to v from (𝐷 + 1)th
color. Hence, the chromatic number of 𝐺 is less than or equal to 𝐷 + 1.

Theorem 14.2.5. For any graph G, 𝜒(𝐺) ≤ 1 + 𝑚𝑎𝑥𝛿(𝐺′), where the maximum is taken over all induced
subgraphs G’ of G.
Proof: The result is obvious for totally disconnected graphs. Let G be an arbitrary n-chromatic graph, 𝑛 ≥
2 Let H be any smallest induced subgraph such that 𝜒( 𝐻 ) = 𝑛. The graph H therefore has the property
that 𝜒(𝐻 − 𝑣) = 𝑛 − 1 for all its points 𝑣. It follows that 𝑑𝑒𝑔𝑣 ≥ 𝑛 − 1 so that 𝛿(H) ≥ n-1 and hence,
n - 1 ≤ 𝛿 (H) ≤ max 𝛿 (H') ≤ max 𝛿 (G'),
the first maximum taken over all induced subgraphs H' of H and the second
over all induced subgraphs G' of G. This implies that
𝜒(𝐺) = 𝑛 ≤ 1 + 𝑚𝑎𝑥𝛿 (𝐺′)

Page 142
14.3. Four-color theorem:
The statement of four-color theorem is given as below:
“Every planar graph can be properly colored using four colors only".
14.4. Summary:
A coloring of a graph is an assignment of colors to its points so that no two adjacent points have
the same color. The set of all points with any one color is independent and is called a colors
class. An n-coloring of a graph G uses n colors; it thereby partitions 𝑽 into n color classes.

14.5. Keywords
Coloring of graphs, chromatic number, n-coloring, Four color theorem.

14.6. Reference:

1. F. Harary, Graph Theory, Addison-Wesley, 1969

2. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science, PHI,
2011.
3. B. Sooryanarayana and G. K. Ranganath, Text book of graph theory, S. Chand and Co. New
Delhi.
4. G. Chartrand and L. Lisniak, Graphs and Digraphs, Wordsworth, [Link], California,
1986.

Page 143
 UNIT– 15
THE FIVE COLOR THEOREM

Structure:

15.0. Objectives

15.1. Introduction

15.2. The Five Color Theorem

15.3. Keywords

15.4. References

15.0. Objectives:
The objective of this unit is to make the learners conversant on Five color theorem.

15.1 Introduction:
The five color theorem is a result from graph theory that given a plane separated into regions, such as a
political map of the countries of a state, the regions may be colored using not more than five colors in such a way
that no two adjacent regions receive the same color. It is not known whether all planar graphs are 4-colorable, they
are certainly 5-colorable. In this unit, we present a proof of Five color theorem.

15.2 The Five Color Theorem

Theorem 15.2.1(A) Every planar graph is 5-colorable.
Proof. We proceed by induction on the number 𝑝 of points. For any planar graph having 𝑝 ≤ 5 points, the result
follows trivially since the graph is 𝑝-colorable.
As the inductive hypothesis we assume that all planar graphs with p points, 𝑝 ≥ 5, are 5-colorable. Let G be a
plane graph with (𝑝 + 1) vertices. We know that, G contains a vertex 𝑣 of degree 5 or less. By hypothesis, the
plane graph 𝐺 − 𝑣 is 5-colorable.
Consider an assignment of colors to the vertices of 𝐺 − 𝑣 so that a 5-coloring results, where the colors are denoted
by 𝑐𝑖 , 1 ≤ 𝑖 ≤ 5. Certainly, if some color, say 𝑐𝑗 , is not used in the coloring of the vertices adjacent with 𝑣, then by
assigning the color 𝑐𝑗 to 𝑣, a 5-coloring of 𝐺 results.
This leaves only the case to consider in which 𝑑𝑒𝑔 𝑣 = 5 and five colors are used for the vertices of 𝐺 adjacent
with 𝑣. Permute the colors, if necessary, so that the vertices colored 𝑐1 , 𝑐2 , 𝑐3 , 𝑐4 and 𝑐5 are arranged cyclically

Page 144
about 𝑣. Now label the vertex adjacent with 𝑣 and colored 𝑐𝑖 by 𝑣𝑖 ,1≤ 𝑖 ≤ 5 (see Fig. 15.2.1(A)).

Fig. 15.2.1(A). A step in the proof of the Five color theorem.

Let 𝐺13 denote the subgraph of 𝐺 − 𝑣 induced by those vertices colored 𝑐1 or 𝑐3. If 𝑣1 𝑎𝑛𝑑 𝑣3 belong to
different components of 𝐺13 , then a 5-coloring of 𝐺 − 𝑣 may be accomplished by interchanging the
colors of the vertices in the component of 𝐺13 containing 𝑣1 .In this 5-coloring, however, no vertex
adjacent with 𝑣 is colored 𝑐𝑖 , so by coloring 𝑣 with the color 𝑐1 , a 5-coloring of G results.
If, on the other hand, 𝑣1 and 𝑣3 belong to the same component of 𝐺13 , then there exists in G a path
between 𝑣1 𝑎𝑛𝑑 𝑣3 all of whose vertices are colored 𝑐1 or 𝑐3. This path together with the path
𝑣1 𝑣 𝑣3 produces a cycle which necessarily encloses the vertex 𝑣2 or both the vertices 𝑣4 and 𝑣5 . In any
case, there exists no path joining 𝑣2 and 𝑣4 , all of whose vertices are colored 𝑐2 or 𝑐4 . Hence, if we let
𝐺24. denote the subgraph of 𝐺 − 𝑣 induced by the vertices colored 𝑐2 or 𝑐4 , then 𝑣2 and 𝑣4 belong to
different components of 𝐺24 . Thus if we interchange colors of the vertices in the component of 𝐺24
containing 𝑣2 , a 5-coloring of 𝐺 − 𝑣 produced in which no vertex adjacent with 𝑣 is colored 𝑐2 .We may
then obtain a 5-coloring of 𝐺 by assigning to 𝑣 the color 𝑐2 .

NOTE: Another proof on The Five color theorem is provided for the better understanding. The students
are suggested to learn any one of the proof, either Theorem 15.2.1(A) (or) Theorem 15.2.1(B)

(OR)

Page 145
Theorem 15.2.1(B)Theorem: Any finite planar graph G can be colored using five colors.
Proof: To prove the theorem, we use induction on the number of vertices of the graph. Let G be a planar
graph with m vertices. Since 𝐺 is a planar graph and connected, there exists at least one vertex of degree
less than or equal to five.
Let v be the vertex of degree ≤ 5, and consider the induced subgraph 𝐺′ of 𝐺 on 𝐺-v. According to the
induction hypothesis, induced subgraph 𝐺′ requires no more than five colors. If the degree of vertex v is
less than 4, then there is no difficulty in proper coloring. But the vertex v has exactly five neighbours and
they are all differently colored as shown in the figure. 15.2.1(B).

Fig. 15.2.1(B)

Suppose there is a path between vertices 𝑎 and c, say 𝑎 → 𝑣1 → 𝑣2 … → 𝑣𝑛 → 𝑐. Color alternatively a by

𝑝1, , 𝑣1 by 𝑝2, , 𝑣2 by 𝑝1, , and so on. Also, according to the property of the planar graph, there is no similar
path between b and d (because it will intersect the path a and c). Hence there is no path of alternating
colors 𝑝2, and 𝑝4 through vertices b and d. So, vertex d can be colored or (painted) with the color 𝑝2, and
vertex b is still with the color 𝑝2, . Now we have color 𝑝4 left over with which we can color vertex v.
Similarly, we can assume that there is no path between a and c and a path between b and d, then we can
color v with the color 𝑝1 or 𝑝3 , instead of 𝑝4 . Hence the theorem.

15.3. Keywords: The five color theorem.

15.4. References
1. F. Harary, Graph Theory, Addison-Wesley, 1969.
2. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science,
PHI, 2011.
3. B. Sooryanarayana and G. K. Ranganath, Text book of graph theory, S. Chand and Co.
New Delhi.
4. G. Chartrand and L. Lisniak, Graphs and Digraphs, Wordsworth, Inc. Belmont,
California,1986.

Page 146
 UNIT – 16
THE CHROMATIC POLYNOMIAL OF A GRAPH

Structure:

16.0. Objectives

16.1. Introduction

16.2. Chromatic polynomial of graphs

16.3. Summary

16.4. Keywords

16.5. Exercises

16.6. References

16.0. Objectives
The objective of this unit is to make the learners conversant on –
 Chromatic polynomial of graphs

16.1. Introduction

The chromatic polynomial of graph G is a polynomial function which defines number of ways a
graph can be colored with some number of colors. We write chromatic polynomial of a graph of
n vertices denoted by 𝒇(𝑮, 𝝀), where we have 𝝀 number of colors.
1. It represents the number of ways we can color vertices of graph with given number of
colors such that no adjacent vertices have same color.
2. It is an important tool in graph theory for studying coloring problems and has various
application in fields like computer science.

Page 147
16.2. Chromatic polynomial:

The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch
of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally
defined by George David Birkhoff to study the four color problem.
The chromatic polynomial of a graph with n vertices is a polynomial 𝑃𝑛 (𝜆)which gives the
number of ways of properly coloring the graph using 𝜆 or fewer colours.

Chromatic polynomial for a Complete Graph

Here we take a complete graph with 𝒗 number of vertices and we have 𝝀 number of colors
𝒄𝟏 , 𝒄𝟐 , 𝒄𝟑 , … , 𝒄𝝀 . So we can say 𝝀 ≥ 𝒗. In a complete graph all vertices are adjacent to each other, so
each of them must be colored with different or dictinct colors.

Theorem 16.2.1. A graph G with n vertices is a complete graph iff its chromatic polynomial is
𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)(𝜆 − 2) … … . (𝜆 − 𝑛 + 1)
Proof: Let G be a complete graph with n vertices 𝑣1 , 𝑣2 , 𝑣3 … … 𝑣𝑛 . We have 𝜆 colors to color the graph
G, the first vertex 𝑣1 can be coloured with any one of the 𝜆 colours, vertex 𝑣2 with any one of remaining
𝜆 - 1 colors and so on. Thus,
𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)(𝜆 − 2) … (𝜆 − 𝑛 + 1)
Conversely, suppose that
𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)(𝜆 − 2) … (𝜆 − 𝑛 + 1)
is a chromatic polynomial of a graph G with 𝑛 vertices. There are 𝜆 different ways of colouring any
selected vertex. A second vertex can be colored properly in (𝜆 − 1) ways, the third in (𝜆 − 2) ways,...
and the 𝑛th in (𝜆 − 𝑛 + 1) ways if every vertex is adjacent to every other vertex. Thus, the graph can
be proved to be complete graph.

Page 148
Theorem 16.2.2. A graph 𝐺 with 𝑛 vertices is a tree iff its chromatic polynomial is
𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)𝑛−1
Proof: We will prove this theorem by mathematical induction on the vertices of 𝐺. Let the graph be a tree
with 𝑛 vertices. The result is true for 𝑛 = 1 and 𝑛 = 2 as for 𝑛 = 1, 𝑃𝑛 (𝜆) = 𝜆 and for 𝑛 = 2,
𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1). Suppose that the result is true for all trees having less than 𝑛 vertices. Now consider a
tree with 𝑛 vertices. Then 𝑇 has at least two pendant vertices. Let 𝑣 be a pendant vertex of 𝑇 and consider
𝑇*= 𝑇 − 𝑣. Then 𝑇* is a tree with (𝑛 − 1) vertices. Hence, by induction hypothesis, the chromatic
polynomial of 𝑇 * is
𝑃𝑛−1 (𝜆) = 𝜆(𝜆 − 1)𝑛−2
Let 𝑣 ′ be the vertex adjacent to 𝑣 in 𝑇. Now add 𝑣 to 𝑇*. Suppose 𝑣 ′ is colored with any one of the
𝜆′ colours. Then 𝑣 can be colored with any one of the remaining (𝜆 − 1) colors.
Thus, the number of ways of coloring of 𝑇 is
𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)𝑛−2 (𝜆 − 1) = 𝜆(𝜆 − 1)𝑛−1
Hence, the result.
Conversely, suppose that the chromatic polynomial of the given graph 𝐺 is

𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)𝑛−1

From the chromatic polynomial of 𝐺, it is clear that every vertex of 𝐺 except one vertex can be colored in
𝜆 − 1 ways. Delete one such vertex 𝑢. Then 𝐺 − 𝑢 is a graph with 𝑛 − 1 vertices whose chromatic
polynomial is
𝑃𝑛−1 (𝜆) = 𝜆(𝜆 − 1)𝑛−2

By induction hypothesis 𝐺 − 𝑢 is a tree.

Now add 𝑢 along with the edges incident on 𝑢 to the graph 𝐺 − 𝑢. Clearly 𝑢 cannot be an isolated
vertex. Hence, 𝑢 is connected to some vertex of 𝐺 − 𝑢. Now we will prove that 𝑢 cannot be connected to
more than one vertex in 𝐺 − 𝑢. Suppose if possible 𝑢 is joined to two vertices in 𝐺 − 𝑢. Since 𝐺 − 𝑢 is
a tree with chromatic polynomial 𝑃𝑛−1 (𝜆) = 𝜆(𝜆 − 1)𝑛−2 and 𝑢 is joined to two vertices of 𝐺 − 𝑢.
Therefore, 𝑢 can be colored in (𝜆 − 2)ways only. But now the chromatic polynomial of 𝐺 is
𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)𝑛−2 (𝜆 − 2)
which is not true. Hence, 𝑢 is joined to only one vertex in 𝐺 − 𝑢. Thus, 𝐺 is a tree.
Theorem 16.2.3. Let 𝑢 and 𝑣 be two non-adjacent vertices in a graph 𝐺. Let 𝐺 ' be a graph obtained by
adding an edge 𝑒 between 𝑢 and 𝑣. Let 𝐺" be a simple graph obtained from 𝐺 by fusing the vertices 𝑢 and
𝑣 together and replacing parallel edges with simple edge.

Page 149
Then,
𝑃𝑛 (𝜆) of 𝐺 = 𝑃𝑛 (𝜆)of 𝐺 ′ + 𝑃𝑛 (𝜆) of 𝐺"

Proof: The number of ways of properly coloring of 𝐺 can be divided into two cases.
Case I: The vertices 𝑢 and 𝑣 are of same color.
Case II: The vertices 𝑢 and 𝑣 are of different colors.
Since the number of ways of proper coloring of G, such that 𝑢 and 𝑣 have different colors = number of
ways of proper coloring of G' and number of ways of proper coloring of G such that 𝑢 and 𝑣 have the
same color = number of ways of proper coloring of 𝐺"

Thus, we have
𝑃𝑛 (𝜆)𝑜𝑓 𝐺 = 𝑃𝑛 (𝜆)𝑜𝑓 𝐺 ′ + 𝑃𝑛 (𝜆) 𝑜𝑓 𝐺"

Corollary: If 𝑒 = (𝑢, 𝑣) is an edge of a simple graph 𝐺, then

𝑃𝑛 (𝜆)𝑜𝑓 𝐺 = 𝑃𝑛 (𝜆)𝑜𝑓 𝐺 − 𝑒 − 𝑃𝑛 (𝜆) 𝑜𝑓 𝐺"

Example 1. Find the chromatic polynomial of the following graph

Solution: To obtain the chromatic polynomial of this graph, we use Theorem 16.2.3. Since, this graph has
non-adjacent vertices, select any pair of non-adjacent vertices in the graph. Suppose we select 𝑣1 and
𝑣3 . Now we draw an edge between 𝑣1 and 𝑣3 to obtain the graph 𝐺 ′ .We will also fuse the vertices 𝑣1 and
𝑣3 to obtain the graph 𝐺" as shown below.

Page 150
Again taking 𝑣2 and 𝑣4 as non –adjacent vertices in Fig(b) and Fig(c) and applying the same procedure,
we have

All the four graphs are new complete graphs, therefore, the chromatic polynomial of the given graph is
the sum of chromatic polynomial of these four complete graphs.
Hence, the chromatic polynomial of the given graph is
𝑃5 (𝜆) = 𝜆(𝜆 − 1)(𝜆 − 2)(𝜆 − 3)(𝜆 − 4) + 2𝜆(𝜆 − 1)(𝜆 − 2)(𝜆 − 3) + 𝜆(𝜆 − 1)(𝜆 − 2)
= 𝜆(𝜆 − 1)(𝜆 − 2)(𝜆2 − 5𝜆 + 7)
Example 2. Find the chromatic polynomial of the complete bipartite graph 𝐾2,5 .
Solution The graph 𝐾2,5 can be drawn as

Page 151
If the vertices 𝑎 and 𝑏 have the same color, then the total number of ways of proper coloring of 𝐾2,5 is
𝜆(𝜆 − 1)5
If 𝑎 and 𝑏 are of different colors, then there are 𝜆(𝜆 − 1)(𝜆 − 2)5 different ways of coloring. Thus,
𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)5 + 𝜆(𝜆 − 1)(𝜆 − 2)5

Example 3. Obtain the chromatic number and chromatic polynomial of the graph given as below:

Solution: Before the solution of this example first we give a statement given below
Suppose that G is an undirected graph with subgraphs 𝐺1 and 𝐺2 . If 𝐺 = 𝐺1 ∪ 𝐺2 and 𝐺1 ∩ 𝐺2 = 𝐾𝑛 , for
some 𝑛 ∈ 𝑍 + , then
[𝑃(𝐺1 , 𝜆)𝑃(𝐺2 , 𝜆)]
𝑃(𝐺, 𝜆) =
𝜆(𝑛)
Here 𝑃(𝐺, 𝜆) denotes the chromatic polynomial of the graph 𝐺 with 𝜆 colour.
We use the above statement to solve the given problem
Let 𝐺1 be the subgraph induced by (𝑏, 𝑐, 𝑑, 𝑒) and 𝐺2 be the subgraph of 𝐺 which is a cycle determined by
(𝑎, 𝑏, 𝑐) that is

Here, 𝐺1 ∪ 𝐺2 = 𝐺 and 𝐺1 ∩ 𝐺2 = (𝑏, 𝑐) = 𝐾2

Page 152
Applying the above statement, we have
[𝑃(𝐺1 ,𝜆)𝑃(𝐺2 ,𝜆)]
𝑃(𝐺, 𝜆) = [∴ 𝑛 = 2]
𝜆(2)

But, 𝑃(𝐺1 , 𝜆) = 𝜆(𝜆 − 1)(𝜆 − 2)(𝜆 − 3)

𝑃(𝐺2 , 𝜆) = 𝜆(𝜆 − 1)(𝜆 − 2)
And, 𝜆(2) = 𝜆(𝜆 − 1)
[∴In factorial notation 𝜆(𝑛) = 𝜆(𝜆 − 1) … . (𝜆 − 𝑛 + 1)]
𝜆(𝜆 − 1)(𝜆 − 2)(𝜆 − 3)𝜆(𝜆 − 1)(𝜆 − 2)
∴ 𝑃(𝐺, 𝜆) =
𝜆(𝜆 − 1)
= 𝜆(𝜆 − 1)(𝜆 − 2)2 (𝜆 − 3)

which is the required chromatic polynomial. The least value of 𝜆 for which 𝑃(𝐺, 𝜆) > 0 is 4, i.e., the
chromatic number is 4.

16.3. Summary:
The chromatic polynomial is described as a function that finds out the number of proper colouring of a graph with
the help of colours. The main property of chromatic polynomial is that it will prove that four colours can be used to
colour every map. They will be coloured in such a way that the same colour should not be shared by a region that
shares a border with another region. There are also a lot of interesting properties of chromatic polynomial. In this
unit, we will learnt some of the main properties.

16.4. Exercise:

1. Write down the chromatic polynomial of the complete bipartite graph 𝐾2,4 .
2. Write down the chromatic polynomial of the complete graph with 6 vertices.
3. Find the chromatic polynomial of the following graph.

4. Find three graphs with chromatic polynomial

𝑃𝑛 (𝜆) = 𝜆5 − 4𝜆4 + 6𝜆3 − 4𝜆2 + 𝜆
5. Prove that the chromatic polynomial of 𝐾2,𝑛 𝑖𝑠

Page 153
 𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)𝑛 + 𝜆(𝜆 − 1)(𝜆 − 2)𝑛
6. Let G be a simple graph with 𝑛 vertices which is regular of degree 𝑟. Prove that chromatic number
𝑛
is greater than or equal to 𝑛−𝑟.

16.5. Keywords: Chromatic polynomial of graph

16.6. References
1. F. Harary, Graph Theory, Addison-Wesley, 1969
2. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science,
PHI, 2011.
3. B. Sooryanarayana and G. K. Ranganath, Text book of graph theory, S. Chand and Co.
New Delhi.
4. G. Chartrand and L. Lisniak, Graphs and Digraphs, Wordsworth, [Link], California,
1986.

Page 154