MODULE-4

GRAPH THEORY
CONTENT
 Prerequisite (undirected graphs)
 Definitions and Examples,
 Graph Isomorphism
 Sub graphs
 Complements
 Vertex degree: Trails and Circuits
 Euler Trails and Circuits
 Paths and cycle
 Hamilton Paths and Cycles
 Planar Graphs
 Graph Colouring
 Chromatic Polynomials

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Prerequisite

Directed Graphs
The diagram (Fig 1.1) consists of four vertices A, B, C,
B D and three edges AB, CD, CA with directions attached to
A
them, the directions being indicated by arrows.

C D Because of attaching directions to the edges, the edge

Fig 1.1 AB has to be interpreted as an edge from the vertex A to B
and it cannot be written as BA.

Similarly, the edge CD is from C to D cannot be written as DC, and the edge CA
from C to A cannot be written as AC. Thus, here, the edges AB, CD, CA are directed
edges
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Prerequisite

CONTD…
The directed edges AB , CD and CA may be represented by the ordered pair (A, B), (C, D) and
(C,A) respectively.

The diagram in Fig 1.1 consists of a nonempty set of vertices, namely 𝐴, 𝐵, 𝐶, 𝐷 , and set
of directed pairs of vertices taken from this set, namely
(𝐴, 𝐵), (𝐶, 𝐷), (𝐶, 𝐴) . Such a diagram is called diagram of a directed graph (or a diagraph).

Definition: A directed graph (or diagraph) is a pair (V, E), where V is a nonempty set
and E is a set of ordered pairs of elements taken from the setV.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Prerequisite

CONTD…
For directed graph (V, E), the elements of V are called vertices (points or nodes) and the
elements od E are called directed edges.

The setV is called the vertex set and the set E is called the directed edge set.

The directed graph (V, E) is also denoted as 𝐷 = 𝑉, 𝐸 𝑜𝑟𝐷 = 𝐷 𝑉, 𝐸 or just D.

For diagram of Fig 1.1

Vertex set 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷 Edge set 𝐸 = 𝐴𝐵, 𝐶𝐷, 𝐶𝐴

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Prerequisite

CONTD…
A B
Whether Fig 1.1 and Fig 1.2 are same?
Fig 1.1 and Fig 1.2 are not same, although both of these
two directed graph have the same vertex set, their
C D
Fig 1.1 directed edges sets are different.
A B

Whether Fig 1.3 is a directed graph?

C D In the directed graph the directed edges need not to be
Fig 1.2 straight line segments; they can be curved lines (arc)
also.
Fig 1.3
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Prerequisite

CONTD…
A B Every directed edge of a diagraph is determined by two
vertices --- a vertex from which it begins and a vertex at which it
ends.
If AB is a directed edge of a diagraph D. A- Initial vertex and B-
C D
Fig 1.1 terminal vertex of [Link] is incident out of A and incident into B.
The directed edge shown in Fig 1.4 is directed loop which
begins and ends at the vertex A.

A BA B Two directed edges having the same initial vertex and the
A same terminal vertex are called parallel directed edges fig
1.5 (a).

(a) (b)
Fig 1.4 Two or more directed edges having the same initial vertex
and the same terminal vertex are called multiple directed
Fig 1.5 edges fig 1.5 (a).
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Prerequisite

CONTD…
Isolated Vertex: (𝒗𝟒 ): A vertex of diagraph which is neither an initial
vertex nor a terminal vertex of any directed edge.

Non-isolated vertex happens to be initial vertex or a terminal

vertex for some directed edges.

A non-isolated vertex which is not a terminal vertex for any directed edge is called source.
A non-isolated vertex which is not a initial vertex for any directed edge is called sink.
𝒗𝟏 𝒂𝒏𝒅𝒗𝟑 are sources. 𝒗𝟐 𝑖𝑠 𝑎 𝑠𝑖𝑛𝑘.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Prerequisite

In degree and Out-degree

If 𝑣 is a vertex of a diagraph D, the number of edges for which
𝑣 is the initial vertex is called the out-degree of 𝒗. 𝒅+ (𝒗)
The number of edges for which 𝑣 is the terminal vertex is called the
in-degree of 𝒗. 𝒅− (𝒗)

𝒅+ 𝒗𝟏 =𝟐 𝒅− 𝒗𝟏 =𝟏 The loop contributes a count 1 to each in-degree and

𝒅+ 𝒗𝟐 =𝟏 𝒅− 𝒗𝟐 =𝟑 out-degree.
𝒅+ 𝒗𝟑 =𝟏 𝒅− 𝒗𝟑 =𝟐 Property 1: In every diagraph D, the sum of the out-degrees of
𝒅+ 𝒗𝟒 =𝟎 𝒅− 𝒗𝟒 =𝟎 all vertices is equal to the sum of the in-degrees of all vertices,
𝒅+ 𝒗𝟓 =𝟐 𝒅− 𝒗𝟓 =𝟏 each sum being equal to the number of edges in D.
𝒅+ 𝒗𝟔 =𝟐 𝒅− 𝒗𝟔 =𝟏
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Prerequisite

Examples
1. Find out the in degrees and out degrees of the vertices of the
diagraph shown in fig 1.8.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

Graphs
A B Fig 1.1 is a directed graph and Fig 2.1 is a undirected Graph
(Graph).

C D The edge AB is determined by the vertices A and B and

Fig 1.1 represented by unordered pair AB = BA .
A B

Definition: A graph is pair 𝑽, 𝑬 , where V is a

nonempty set and E is a set of unordered pairs of
D
elements taken from the setV.
C
Fig 2.1

The graph is denoted by 𝑮 = 𝑽, 𝑬 , 𝑮 = 𝑮 𝑽, 𝑬 , 𝑮.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

Graph
According to the definition of a graph/diagraph, the vertex set in a graph/diagraph
has to be nonempty set but the edge set can be empty.
A
A
B C
(a) (b)
Fig 2.2

A graph containing no edges is called a null graph (Fig 2.2 (a)). A null graph with only
one vertex is called a trivial graph (Fig 2.2 (b)).

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

Graphs
Draw the graphs with four vertices A, B, C, D with AB, AC, AD, BC and CD.
B
A
A C

B C D
D
(a) (b)
Fig 2.3
The way one draws a diagram of a graph is basically immaterial. There can be more than one diagram for
the same [Link] they represent the same graph since each convey the same information.
A graph with a finite number of vertices and finite number of edges is called finite graph otherwise is
called infinite graph.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

Order and size of graph

The number of vertices in a graph is called order of the graph and the number of edges in the
graph are called its size.
Cardinality of V, 𝑽 is the order.
Cardinality of E, 𝑬 is the size.

A graph of order 𝑛 and size 𝑚 is called a (𝒏, 𝒎) graph.

A null graph with 𝑛 vertices is a 𝑛, 0 graph.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

End vertices, loop, multiple edges

The fig 2.4 has 4 vertices 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 and six edges
𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 .

𝑣1 , 𝑎𝑛𝑑 𝑣2 are end vertices of the edge 𝑒1 . Written as 𝑒1 =

𝑣1 , 𝑣2 , Similarly other end vertices can be defined.

An edge such as 𝑒4 is called loop, 𝑒4 = 𝑣3 , 𝑣3 .

Fig 2.4

The both edges 𝑒5 , 𝑒6 have same end vertices 𝑣1 , 𝑣4 such edges are called parallel edges. 𝑒5 =
𝑣1 , 𝑣4 , 𝑒6 = 𝑣1 , 𝑣4 .
If in a graph there are two or more edges with the same end vertices, the edges are called
multiple edges.
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Definition & Examples

Simple graph, Multiple graph, General graph

Simple Graph: A graph does not contain loops and multiple edges is called a simple graph.
A graph which does not contains a loops is called a loop-free graph.

Multigraph: A graph which contains multiple edges but no loops is called multigraphs.

General Graph: A graph which contains multiple edges or loops (or both) is called general graphs.
Fig 2.1 is a simple graph, Fig 2.4 is a general graph, Fig 2.5 is Multigraph graph
A B

C D Fig 2.4 Fig 2.5

Fig 2.1
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Definition & Examples

Adjacent edges and vertices

The two non parallel edges are said to be adjacent edges if they are incident on a common
vertex.
Two vertices are said to be adjacent vertices if there is an edge joining them.

In Fig 2.6, A and B are adjacent vertices and 𝑒1 and 𝑒2 are

adjacent edges.

A and C are not adjacent vertices and 𝑒1 and 𝑒3 are not adjacent
edges.
Fig 2.6

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

Complete Graph
Def: A simple graph of order ≥ 2 in which there is an edge between every pair of vertices is
called a complete graph. OR
A complete graph is a simple graph in which every pair of distinct vertices are adjacent.
A complete graph with 𝒏 ≥ 𝟐 vertices is denoted by 𝒌𝒏 .
Following are the complete graph with 2, 3,, 4 and 5 vertices are shown below

𝑲𝟓 is called the
Kuratowski’s first
graph

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Fig 2.7
Definition & Examples

Bipartite graph
Def: Suppose a simple graph G is such that its vertex set V is the union of two mutually disjoint
nonempty sets 𝑉1 𝑎𝑛𝑑 𝑉2 which are such that each edges in G joins a vertex in 𝑉1 and a vertex 𝑉2 .
Then G is called a bipartite graph.
If E is the edge set of this graph, the graph is denoted by 𝐺 = (𝑉1 , 𝑉2 ; 𝐸), or 𝐺 = 𝐺(𝑉1 , 𝑉2 ; 𝐸).
The sets 𝑉1 𝑎𝑛𝑑 𝑉2 are called bipartites of the vertex setV.

𝑽 = 𝑨, 𝑩, 𝑪, 𝑷, 𝑸, 𝑹, 𝑺 , 𝑽𝟏 = 𝑨, 𝑩, 𝑪 , 𝑽𝟐 = 𝑷, 𝑸, 𝑹, 𝑺
𝑬 = 𝑨𝑷, 𝑨𝑸, 𝑨𝑹, 𝑩𝑹, 𝑪𝑸, 𝑪𝑺 .
(i) 𝑉1 𝑎𝑛𝑑 𝑉2 are disjoint.
(ii) Every edge in G is a join of a vertex in 𝑉1 and a vertex in 𝑉2 .
(iii) G contains no edge that joins two vertices both of which are in
𝑉1 𝑎𝑛𝑑 𝑉2 .

DISCRETE MATHEMATICS & GRAPH THEORY Fig 2.8 3/29/2023

Definition & Examples

Complete Bipartite graph

Def: A bipartite graph 𝐺 = (𝑉1 , 𝑉2 ; 𝐸) is called a complete bipartite graph if there is an edge between
every vertex in 𝑉1 and every vertex in 𝑉2 .

A complete bipartite graph 𝐺 = (𝑉1 , 𝑉2 ; 𝐸) in which the bipartites 𝑉1 𝑎𝑛𝑑 𝑉2 contain 𝑟 and 𝑠
vertices respectively, with 𝑟 ≤ 𝑠, is denoted by 𝐾𝑟,𝑠 .

𝐾𝑟,𝑠 has 𝑟 + 𝑠 vertices and 𝑟𝑠 edges; that is 𝐾𝑟,𝑠 is of order 𝑟 + 𝑠 and size 𝑟𝑠; it is therefore a
𝑟 + 𝑠, 𝑟𝑠 graph.

𝑲𝟑,𝟑 is called the

Kuratowski’s second graph

DISCRETE MATHEMATICS & GRAPH THEORY Fig 2.9 3/29/2023

Definition & Examples

Example
1. Draw a diagram of the graph 𝑮 = 𝑮(𝑽, 𝑬) in each of the following cases.
(i) 𝑽 = 𝑨, 𝑩, 𝑪, 𝑫 , 𝑬 = 𝑨, 𝑩 , 𝑨, 𝑪 , 𝑨, 𝑫 , (𝑪, 𝑫)
(ii) 𝑽 = 𝒗𝟏 , 𝒗𝟐 , 𝒗𝟑 , 𝒗𝟒 , 𝒗𝟓 , 𝑬 = 𝒗𝟏 , 𝒗𝟐 , 𝒗𝟏 , 𝒗𝟑 , 𝒗𝟐 , 𝒗𝟑 , (𝒗𝟒 , 𝒗𝟓 )
(iii) 𝑽 = 𝑷, 𝑸, 𝑹, 𝑺, 𝑻 , 𝑬 = 𝑷, 𝑺 , 𝑸, 𝑹 , 𝑸, 𝑺
(iv) 𝑽 = 𝒗𝟏 , 𝒗𝟐 , 𝒗𝟑 , 𝒗𝟒 , 𝒗𝟓 , 𝒗𝟔 , 𝑬 =
𝒗𝟏 , 𝒗𝟒 , 𝒗𝟏 , 𝒗𝟔 , 𝒗𝟑 , 𝒗𝟐 , 𝒗𝟒 , 𝒗𝟔 , 𝒗𝟑 , 𝒗𝟓 , (𝒗𝟐 , 𝒗𝟓 )

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

Example
2. Let P, Q, R, S, T represent five cricket teams. Suppose that the teams P, Q, R have played one game with
each other, and the teams P, S,T have played one game with each other. Represent this in a graph.
Hence determine (i) the teams that have not played with each other (ii) the number of games played by
each team.

Solution: Let the team represents vertices and edge represents the playing. Then the graph represents the given situation is as
shown below.
There is no edge between Q and S, Q andT, R and S, R andT.
Therefore the teams Q and S, Q andT, R and S, R andT have not played together.

The degree of Q, R, S,T is 2 and degree of P is 4.

Therefore Q, R, S,T played two games each and P played 4 games

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

Example
3. Which of the following is a complete graph?

Solution: (a) is not complete graph- it is not a simple graph, no edge between A and C
(b) Is complete graph- there is an edge between every pair of vertices

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples
𝟐
4. If 𝑮 = 𝑮(𝑽, 𝑬) is a simple graph, prove that 𝟐 𝑬 = 𝑽 − 𝑽.

Solution:
 Each edge of a graph is determined by pair of vertices.
 In simple graph there are no multiple edges
 The number of edges cannot exceed the number of vertices.
𝑛 1
 The number of pairs of vertices that can be choosen from 𝑛 vertices is 𝐶2 = 𝑛(𝑛 − 1)
2
1
 Thus, for a simple graph with 𝑛 (≥ 2) vertices, the number of edges cannot exceed 𝑛(𝑛 − 1).
2

Accordingly if the simple graph G has 𝑛 vertices and 𝑚 edges, then 𝑚 ≤ 1/2𝑛(𝑛 − 1)
Therefore 2𝑚 ≤ 𝑛2 − 𝑛 , that is 𝟐 𝑬 = 𝑽 𝟐 − 𝑽 .

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples
𝟏
5. Show that a complete graph with 𝒏 vertices, namely 𝑲𝒏 , has 𝒏(𝒏 − 𝟏) edges.
𝟐

Solution:
In a complete graph, there exist one edge between every pair of vertices.
Therefore
Number of of edges = Number of pair of vertices
𝟏
If 𝑛 is number of vertices, then number of pair of vertices is 𝒏(𝒏 − 𝟏)
𝟐
Thus the number of edges is a complete graph is with 𝒏 vertices is
𝟏
𝒏(𝒏 − 𝟏)
𝟐

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

6. show that a simple graph of order 𝒏 = 𝟒 and size 𝒎 = 𝟕 and a complete

graph of order 𝒏 = 𝟒 and size 𝒎 = 𝟓 do not exist.

Solution:
𝟏
For 𝑛 = 4, m= 𝒏 𝒏−𝟏 =𝟔.
𝟐

Since 𝒎 = 𝟕 exceeds this number, a simple graph of order 4 and size 7 do not exist.

𝟏
Similarly, since 𝒎 = 𝟓 is not equal to 𝒏 𝒏 − 𝟏 = 𝟔, a complete graph od
𝟐
order 4 and size m=5 does not exist.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples
7. Which of the following is a bipartite graph?
P Q A D

S B (b) C
Solution: R (a)

(a) Is a bipartite graph 𝑽 = 𝑷, 𝑸, 𝑹, 𝑺 , 𝑽𝟏 = 𝑷, 𝑺 , 𝑽𝟐 = 𝑸, 𝑹

8. How many vertices and how many edges are there in the complete
bipartite graph 𝑲𝟒,𝟕 and 𝑲𝟕,𝟏𝟏 .?
Solution:
11 vertices and 28 edges
18 vertices and 77 edges.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

9. Show that a simple graph of order 𝒏 = 𝟒 and size 𝒎 = 𝟓 cannot be a

bipartite graph.

Solution:
A simple graph to be bipartite graph 4𝑚 ≤ 𝑛2
4𝑚 = 20 and 𝑛2 = 16.

So that 4𝑚 > 𝑛2 , therefore the given simple graph cannot be bipartite graph.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Definition & Examples

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

Vertex Degree and Handshaking Property

Let 𝐺 = (𝑉, 𝐸) be a graph and 𝑣 be a vertex of G. Then, the number of edges of G that are
incident on 𝑣 (that is, the number of edges that join 𝑣 to other vertices of G) with the loops
counted twice is called the degree of the vertex 𝑣 and is denoted by deg(𝑣), or 𝑑(𝑣).

𝑑 𝑣1 = 3, 𝑑 𝑣2 = 4, 𝑑 𝑣3 = 4, 𝑑 𝑣4 = 3

Degree sequence of a graph is 3, 3, 4, 4. (non-decreasing order).

Fig 4.1

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples

Isolated vertex, pendant Vertex

A vertex is a graph which is not an end vertex of any edge of the graph is called an
isolated vertex.
A vertex of degree 1 is called a pendent vertex. An edge incident on a pendant vertex
is called a pendant edge.
In Fig 4.2.𝑣4 , 𝑣6 are isolated vertex. 𝑣5 , 𝑣7 are pendent vertices. And
edge 𝑒4 , 𝑒5 are pendant edges.

In Null graph every vertex is a isolated vertex .

Fig 4.2
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Definition & Examples

Regular Graph
A graph in which all the vertices are of the same degree 𝑘 is called a regular graph of
degree 𝑘. Or 𝑘 − 𝑟𝑒𝑔𝑢𝑙𝑎𝑟 𝑔𝑟𝑎𝑝ℎ.
Draw 2-regular, and 4-regular graph.
2-regular 3-regular 4-regular

Fig 4.3

This 3-regular graph is called Petersen graph. Which has 10 vertices and 15 edges.

DISCRETE MATHEMATICS & GRAPH THEORY Fig 4.4 3/29/2023

Definition & Examples
The graph in Fig 4.4 is a cubic graph with 8 = 23 vertices. This
particular graph is called the three-dimensional hypercube and is
denoted by 𝑄3 .

In general, for any positive integer k, a loop-free k-regular graph with 2𝑘

vertices is called the k-dimensional hypercube (or k-cube) and is denoted by
𝑄𝑘 .
Fig 4.4
Hhandshaking property: The sum of the degrees of all the vertices in a graph is an even
number; and this number is equal to twice the number of edges in the graph. (First
theorem of graph theory)
For a Graph G=G(V, E). σ𝒗∈𝑽 𝒅𝒆𝒈 𝒗 = 𝟐 𝑬
If several people shake hands, the total number of hands shake must be even.

3/29/2023
DISCRETE MATHEMATICS & GRAPH THEORY
Definition & Examples
Theorem: Prove that the sum of the degrees of all the vertices in a graph is an even number
and this number is equal to twice the number of edges in the graph.
෍ 𝒅𝒆𝒈 𝒗 = 𝟐 𝑬
𝒗∈𝑽

Proof: Since the degree of a vertex is the number of edges incident with that vertex,
the sum of degree counts the total number of times an edge is incident with a vertex.
Since every edge is incident with exactly two vertices, each edge counted twice, once at each end.
Therefore, the sum of the degrees is equal twice the number of edges.

෍ 𝒅𝒆𝒈 𝒗 = 𝟐 𝑬
𝒗∈𝑽

Note: this proof applies if multiple edges and loops are present.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples
Theorem: In every graph, the number of vertices of odd degrees is even.

Proof: If a graph has a 𝑛 vertices we know by hand shaking property that

σ𝑛𝑖=1 deg(𝑣𝑖 ) = 2𝑒where 𝑒 is the number of edges.

Now let σ𝑛𝑖=1 deg(𝑣𝑖 ) = σ𝑘𝑖=1 deg(𝑣𝑖 ) + σ𝑛𝑖=𝑘+1 deg(𝑣𝑖 ) −− −1

[𝑖 = 1,2 … 𝑘 𝑎𝑟𝑒 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 𝑤𝑖𝑡ℎ 𝑒𝑣𝑒𝑛 𝑑𝑒𝑔𝑟𝑒𝑒 𝑎𝑛𝑑, 𝑘, 𝑘 + 1, … 𝑛 𝑎𝑟𝑒 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 𝑤𝑖𝑡ℎ 𝑜𝑑𝑑 𝑑𝑒𝑔𝑟𝑒𝑒]
The sum on the left hand side of (1) is twice the number of edges. As such, this sum is even.

2𝑒 = σ𝑘𝑖=1 deg(𝑣𝑖 ) + σ𝑛𝑖=𝑘+1 deg(𝑣𝑖 )

The first sum on the right hand side is the sum of the degrees of vertices with even degree. As such, this sum is also even.
Therefore, the second sum in the right hand side must also be even, that is
𝒏
12 = 8 + ?
෍ 𝒅𝒆𝒈(𝒗𝒊 ) = 𝐞𝐯𝐞𝐧.
𝒊=𝒌+𝟏 1+3=4,
But each 𝒅𝒆𝒈 𝒗𝒌+𝟏 . 𝒅𝒆𝒈 𝒗𝒌+𝟐 …….n is odd. Therefore number of terms must be even. 1+3+5=9
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Definition & Examples

1. For a graph shown below indicate the degree of each vertex and verify
handshaking property.

Solution: deg 𝑎 = 3, deg 𝑏 = 2, deg 𝑐 = 4, deg 𝑑 = 2

deg 𝑒 = 0, deg 𝑓 = 2, deg 𝑔 = 2, deg ℎ = 1
Note that, 𝑒 is a isolated vertex and ℎ is a pendent vertex.

Sum of the degree of vertices =16

Number of edges = 8

Thus, 16 = 2 × 8

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples
2. For a graph 𝑮 = 𝑮(𝑽, 𝑬), what is the largest possible value for 𝑽 if 𝑬 = 𝟏𝟗 and 𝐝𝐞𝐠(𝒗) ≥ 𝟒 for all 𝒗 ∈
𝑽?

Solution: We know by hand shaking property

𝑛

෍ deg(𝑣𝑖 ) = 2𝑒
𝑖=1
Given that, In this graph e = 𝐸 = 19. and degree of all vertices are greater than or equal to 4.
Let 4 + 4 + ⋯ … . ≤ 2𝑒
4 𝑉 ≤ 2 × 19

𝑉 ≤ 38/4

𝑉 ≤ 9.5
Thus, the largest possible value of 𝑉 is 9

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Definition & Examples
Problems:
1. Find the degree of all the vertices of the graph shown below, verify handshaking property.

2. Verify the handshaking property for the graph shown below

3. Are the following graphs regular?

4. Draw the diagram of a graph where the degrees of the vertices are 1, 1, 1, 2, 3, 5, 5, 7
5. For a graph 𝑮 = 𝑮(𝑽, 𝑬), what is the largest possible value for 𝑽 if 𝑬 = 𝟑𝟓 and 𝐝𝐞𝐠(𝒗) ≥ 𝟑 for all 𝒗 ∈ 𝑽?

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Isomorphism

Isomorphism
Consider a graph 𝐺 = (𝑉, 𝐸) and 𝐺 ′ = 𝑉 ′ , 𝐸 ′ . Suppose there exists a function 𝑓: 𝑉 → 𝑉 ′ such that
(i) 𝑓 is one-to-one correspondence
(ii) For all vertices A, B of G, 𝐴, 𝐵 is an edge of G if and only if 𝑓 𝐴 , 𝑓(𝐵) is an edge of 𝐺 ′ .
Then 𝑓 is called an isomorphism between 𝐺 𝑎𝑛𝑑 𝐺 ′ . And we say that 𝐺 𝑎𝑛𝑑 𝐺 ′ are isomorphic graphs.

In other words, two graphs 𝐺 𝑎𝑛𝑑 𝐺 ′ are said to be isomorphic (to each other) if there is one-to-one
correspondence between their vertices and between their edges such that adjacency of vertices is preserved.

Such graph will have same structure; they differ only in the way their vertices and edges are labelled or only in
the way they represented geometrically.

When 𝑮 𝒂𝒏𝒅 𝑮′ are isomorphic, we write 𝑮 ≅ 𝑮′ .

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Isomorphism

Fig. 5.1

In graphs shown above Fig [Link] the following

one-to-one correspondence between the vertices of these two graphs
𝐴 ↔ 𝑃, 𝐵 ↔ 𝑄, C↔ 𝑅, D↔ 𝑆
Under this correspondence, the edge in two graphs correspond with each other, as indicated below:
𝐴, 𝐵 ↔ 𝑃, 𝑄 , 𝐴, 𝐶 ↔ 𝑃, 𝑅 , 𝐴, 𝐷 ↔ 𝑃, 𝑆
𝐵, 𝐶 ↔ 𝑄, 𝑅 , 𝐵, 𝐷 ↔ 𝑄, 𝑆 , 𝐶, 𝐷 ↔ 𝑅, 𝑆
Therefore two graphs are isomorphic.
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Graph Isomorphism

Fig. 5.2
We observe that both of these two graphs have same number of vertices but different number of edges. Therefore, although there can exist one-
to-one correspondence between vertices, there cannot be one-to-one correspondence between [Link] graphs are not isomorphic.

From the definition of isomorphism of graphs, it follows that if two graphs are isomorphic then they must have:
1. The same number of vertices
2. The same number of edges
3. An equal number of vertices with a given degree
These conditions are necessary but not sufficient.

In particular, two graphs of the same order and the same size need not be isomorphic. Consider the two graphs shown below fig5.3
Both of these graphs are order 4 and size 3. But the two graphs are not
isomorphic.
Fig. 5.3
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Graph Isomorphism

Note:
1. Every two complete graphs, with the same number of vertices are isomorphic.
2. Any two complete bipartite graphs with bipartite containing 𝑟 𝑎𝑛𝑑 𝑠 vertices
are isomorphic.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Isomorphism

1. Prove that the graphs shown below are isomorphic.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Isomorphism
2. Verify that the two graphs shown below are isomorphic.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Isomorphism

3. Show that the following two graphs are isomorphic.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Isomorphism

4. Show that the following two graphs are isomorphic.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Isomorphism

5. Show that the following two graphs are not isomorphic.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Isomorphism
6. Show that the following two graphs are not isomorphic.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

7. Show that the following two graphs are not isomorphic.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

8. Show that the two graphs need not to be isomorphic even if they have the
same number of vertices, the same number of edges and equal number of
vertices with the same degree.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

1
4

2
5

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

7

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

1

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

4

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

7

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Subgraphs

Subgraphs
Given two graphs 𝐺 𝑎𝑛𝑑 𝐺1 , we say that 𝐺1 is a subgraph of G if the following condition
holds.
1. All the vertices and all the edges of 𝐺1 are in G.
2. Each edge of 𝐺1 has the same end vertices in G as in 𝐺1 .

Consider two graph in Fig.6.1 (a) and (b), we

observe that
All vertices and all edges of the graph 𝐺1 are in the graph
G.
Fig.6.1 Every edge in 𝐺1 has the same end vertices in G as in 𝐺1 .
Therefore, 𝐺1 is a subgraph of G.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Subgraphs

Spanning subgraphs
Given a graph 𝐺 = (𝑉, 𝐸), if there is a subgraph 𝐺1 = (𝑉1 , 𝐸1 ) of G such that 𝑉1 = 𝑉,
then 𝐺1 is called a spanning subgraph of G.

In other words, a subgraph 𝐺1 of a graph 𝐺 is a spanning subgraph of G whenever 𝐺1 contains all

vertices of [Link], a graph and all its spanning subgraphs have the same vertex set.
Every graph is its own spanning subgraph.

Fig 6.2
(b) Is spanning subgraph of (a)
(c) Is not spanning subgraph of (a)

Fig.6.2
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Subgraphs

Induced subgraphs
Given a graph 𝐺 = (𝑉, 𝐸), suppose there is a subgraph 𝐺1 = (𝑉1 , 𝐸1 ) of 𝐺 such that every edge
of 𝐴, 𝐵 of 𝐺, where 𝐴, 𝐵 ∈ 𝑉1 is an edge of 𝐺1 also. Then 𝐺1 is called an induced subgraph
of 𝐺 (induced by 𝑉1 ) and is denoted by < 𝐴 >.

subgraph 𝐺1 = (𝑉1 , 𝐸1 ) of 𝐺 = (𝑉, 𝐸) is not an induced subgraph of 𝐺 if for some 𝐴, 𝐵 ∈ 𝑉1 ,

there is an edge of 𝐴, 𝐵 which is in 𝐺 𝑏𝑢𝑡 𝑛𝑜𝑡 𝑖𝑛 𝐺1 .

Fig 6.3
(b) Is induced subgraph of (a)
(c) Is not induced subgraph of (a)
Fig.6.3
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Subgraphs

Edge disjoint and Vertex-disjoint Subgraphs

Let 𝐺 be a graph and 𝐺1 and 𝐺2 be two subgraphs of 𝐺.Then:
1. 𝐺1 and 𝐺2 are said to be edge-disjoint if they do not have any edge in common.(may
have common vertices).
2. 𝐺1 and 𝐺2 are said to be Vertex-disjoint if they do not have any common edge and
common vertex.
Subgraphs that have no vertices in common cannot possibly have edges in common. That is, vertex
disjoint subgraphs must be edge disjoint also but converse is not true.

Fig 6.4. (b) and (c) are edge disjoint but not
vertex disjoint subgraphs.

Fig.6.4
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Subgraphs

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Subgraphs

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Subgraphs

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Complements

Complement of a subgraph
Given a graph G and a subgraph 𝐺1 of G, the subgraph of G obtained by deleting from G all the
edges that belong to 𝐺1 is called the complement of 𝑮𝟏 in G; it is denoted by 𝐺 − 𝐺1 , or 𝐺1 .

If 𝐸1 is the set of all edges of 𝐺1 , then the compliment of 𝐺1 in G is given by 𝐺1 = G −

𝐸1 .

In fig 8.1 (a). Let 𝐺1 be the subgraph of G

shown by thick lines in this figure. The
compliment of 𝐺1 in G, namely 𝐺1 , is as shown
in Fig. 8.1 (b).
Fig 8.1

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Complements

Complement of a simple graph

We know that, every simple graph of order 𝑛 is a subgraph of the complete graph 𝐾𝑛 . If G is a simple graph of
order 𝑛, then the complement of G in 𝐾𝑛 is called the complement of G; it is denoted by 𝐺 .

Thus, the complement 𝐺 of a simple graph G with 𝑛 vertices is that graph which is obtained by deleting
those in 𝐾𝑛 which belong to [Link] 𝐺 = 𝐾𝑛 − 𝐺.

Evidently 𝐾𝑛 , G and 𝐺 have the same vertex set, and two vertices are adjacent in G if and only if they are
not adjacent in 𝐺 . Obviously, 𝐺 is also a simple graph and the complement of 𝐺 is G;

Fig 8.2 (a) is complete graph 𝐾4 . A simple graph

of order 4 is shown in (b), the complement 𝐺 of
G is shown in (c).

Fig &8.2
DISCRETE MATHEMATICS GRAPH THEORY 3/29/2023
Complements

Fig 8.3 (a), a graph of order 6 is shown as a subgraph of 𝐾6 , the edges of G is being shown

in thick lines. Its complement 𝐺ҧ is shown in Fig 8.3 (b). This graph is known as David

graph.

Fig 8.3

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Complements

1. Show that the complement of a bipartite graph need not to be a bipartite graph.

Solution: Fig 8.4 (a) shows a bipartite graph which is of order 5. The complement of
this shown in Fig 8.4 (b), this is not bipartite.

Fig 8.4

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Complements

ഥ is 80,
2. Let G be a simple graph of order 𝒏. If the size of G is 56 and the size of 𝑮
what is 𝒏.
Solution: we know that 𝐺 = 𝐾𝑛 − 𝐺.

𝑠𝑖𝑧𝑒 𝑜𝑓𝐺 = 𝑠𝑖𝑧𝑒 𝑜𝑓 𝐾𝑛 − 𝑠𝑖𝑧𝑒 𝑜𝑓 𝐺.

1
Size of 𝐾𝑛 (number of edges is 𝐾𝑛 ) is 𝑛(𝑛 − 1)
2
1
80 = 𝑛(𝑛 − 1)-56
2
𝑛 = 17

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Complements

Problems
1

3
4

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree:Trails and Circuits

Walks and their classification

In this section, we consider five important subgraphs of a graph, called a walk, a trail, a circuit, a path and
a cycle. These subgraphs play a major role in studies concerned with connected graphs to be introduced in
the next section.

Walk
Let G be a graph having at least one edge. In G, consider a finite, alternating sequence of the vertices and edges of the form

𝑣𝑖 𝑒𝑗 𝑣𝑖+1 𝑒𝑗+1 𝑣𝑖+2 𝑒𝑗+2 … … . 𝑒𝑘 𝑣𝑚 .

Which begins and ends with vertices and which is such that each edge in the sequence is incident in the vertices preceding
and following it in the sequence. Such a sequence is called a walk in G.
 In a walk, a vertex or an edge (or both) can appear more than once.

 The number of edges present in a walk is called its length.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree:Trails and Circuits

For example, consider the graph shown below

Fig 8.4
In this graph:

1. The sequence 𝝂𝟏 𝒆𝟏 𝝂𝟐 𝒆𝟐 𝝂𝟑 𝒆𝟖 𝝂𝟔 is a walk of length 3 (because, this walk contains 3 edges: 𝒆𝟏 𝒆𝟐 𝒆𝟖 ). In this walk, no vertex
and no edge is repeated.
2. The sequence 𝝂𝟏 𝒆𝟒 𝝂𝟓 𝒆𝟑 𝝂𝟐 𝒆𝟐 𝝂𝟑 𝒆𝟓 𝝂𝟓 𝒆𝟔 𝝂𝟒 is a walk of length 5. In this walk the vertex 𝝂𝟓 is repeated, but no edge is
repeated
3. The sequence 𝝂𝟏 𝒆𝟏 𝝂𝟐 𝒆𝟑 𝝂𝟓 𝒆𝟑 𝝂𝟐 𝒆𝟐 𝝂𝟑 is a walk of length 4. In this walk the edge 𝒆𝟑 is repeated and the vertex 𝝂𝟐 is
repeated.
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Vertex degree:Trails and Circuits

 The vertex with which a walk begins is called the initial vertex (or the origin) of the walk

 and the vertex with which a walk ends is called the final vertex (or the terminus) of the walk.

 The initial vertex and the final vertex of a walk are together called its terminal vertices.

 The terminal vertices of a walk need not be distinct. Nonterminal vertices of a walk are called its internal vertices.

 A walk having u as the initial vertex and 𝜈 as the final vertex is called a walk from u to 𝜈, or briefly a u- 𝜈 walk.

 A walk that begins and ends at the same vertex is called a closed walk. In other words, a closed walk is a walk in which the

terminal vertices are coincident. A walk which is not closed is called an open walk. In other words, an open walk is a walk
that begins and ends at two different vertices.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree:Trails and Circuits

For example, in the graph shown in Fig 8.4 , 𝜈1 𝑒1 𝜈2 𝑒3 𝜈5 𝑒4 𝜈1 is closed walk 𝜈1 𝑒1 𝜈2 𝑒2 𝜈3 𝑒5 𝜈5 is an open walk.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree:Trails and Circuits

Trail and circuit

As mentioned before, in a walk, vertices and/or edges may appear more than once. If in an open walk no edge appears
more than once, then the walk is called a trail. A closed walk in which no edge appears more than once is called a
circuit.
For example, in Fig 8.4 , the walk
𝜈1 𝑒1 𝜈2 𝑒3 𝜈5 𝑒3 𝜈2 𝑒2 𝜈3 (shown separately in figure 8.5
(a) is an open walk but not a trail (because, in this walk, the
edge 𝑒3 is repeated)
a

The walk 𝜈1 𝑒4 𝜈5 𝑒3 𝜈2 𝑒2 𝜈3 𝑒5 𝜈5 𝑒6 𝜈4 (shown separately

in figure 8.5 (b) is an open walk which is a trail.

DISCRETE MATHEMATICS GRAPH THEORYb

Fig&8.5 3/29/2023
Vertex degree:Trails and Circuits

In Figure 8.4, the walk

𝜈1 𝑒1 𝜈2 𝑒3 𝜈5 𝑒3 𝜈2 𝑒2 𝜈3 𝑒5 𝜈5 𝑒4 𝜈1 (shown separately in
figure (c) is a closed walk but not a circuit (because 𝑒3 is
repeated)

The walk ν1 e1 ν2 e3 ν5 e3 ν2 e7 ν4 e6 ν5 e4 ν1 (shown separately in

figure (d) is a closed walk which is a circuit.

d
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Vertex degree: Path and Cycle

Path and cycle

A trail in which no vertex appears more than once is called a path.

A circuit in which the terminal vertex does not appear as an internal vertex and no internal vertex is repeated is called a

cycle.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Path and Cycle

(a)) (b))

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Path and Cycle

The following facts are to be emphasized.

1. A walk can be open or closed. In a walk (closed or open), a vertex and/or an edge can appear more than once.

2. A trail is an open walk in which a vertex can appear more than once but an edge cannot appear more than once.

3. A circuit is closed walk in which a vertex can appear more than once but an edge cannot appear more than once.

4. A path is an open walk in which neither a vertex nor an edge can appear more than once. Every path is a trail, but a trail need not

be a path.

5. A cycle is closed walk in which neither a vertex nor an edge can appear more than once. Every cycle is circuit; but, a circuit need

not be a cycle.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Path and Cycle

The following results are obvious:

 If cycle contain only one edge, it has to be a loop.

 Two parallel edges (when they occur) form a cycle.

 In a simple graph, a cycle must have at least three edges. (A cycle formed by three edges

is called a triangle)

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Path and Cycle
1. For the graph given below, indicate the nature of the following walks.
(i) 𝒗𝟏 𝒆𝟏 𝒗𝟐 𝒆𝟐 𝒗𝟑 𝒆𝟐 𝒗𝟐
(ii) 𝒗𝟒 𝒆𝟕 𝒗𝟏 𝒆𝟏 𝒗𝟐 𝒆𝟐 𝒗𝟑 𝒆𝟑 𝒗𝟒 𝒆𝟒 𝒗𝟓
(iii) 𝒗𝟏 𝒆𝟏 𝒗𝟐 𝒆𝟐 𝒗𝟑 𝒆𝟑 𝒗𝟒 𝒆𝟒 𝒗𝟓
(iv) 𝒗𝟏 𝒆𝟏 𝒗𝟐 𝒆𝟐 𝒗𝟑 𝒆𝟑 𝒗𝟒 𝒆𝟕 𝒗𝟏
(v) 𝒗𝟔 𝒆𝟓 𝒗𝟓 𝒆𝟒 𝒗𝟒 𝒆𝟑 𝒗𝟑 𝒆𝟐 𝒗𝟐 𝒆𝟏 𝒗𝟏 𝒆𝟕 𝒗𝟒 𝒆𝟔 𝒗𝟔

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Path and Cycle

2. Consider the graph shown below. Find all paths from vertex A to vertex R. also,
indicate their lengths.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Path and Cycle

3. Determine the number of different paths of length 2 in the graph shown below.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Path and Cycle
Problems (9)
1.

2.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Connected and Disconnected Graphs

Answer for the previous problems

1

3
4

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Connected and Disconnected Graphs

Connected and Disconnected Graphs

Consider a Graph G of order greater than or equal to two. Two vertices in G are said to be
connected if there is at least one path from one vertex to the other.

We say that a graph G is a connected graph if every pair if every pair of distinct vertices in G are connected.
Otherwise, G is called a disconnected graph.

In other words, a graph G is said to be (i) connected if there is a at least one path between every two distinct
vertices in G, and (ii) disconnected if G has at least one pair of distinct vertices between which there is no path.

A graph G is connected if we can reach any vertex of G from any other vertex of G by travelling along the edges,
and disconnected otherwise.
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Connected and Disconnected Graphs

Example: Graph shown in Fig 9.1 (a) is connected whereas the graph shown in fig 9.1 (b) is
disconnected.

Fig. 9.1
NOTE:
1. It is obvious that in a graph G all walks and, therefore, all trails, all circuits, all paths and all cycles ( when they exist) are
connected subgraphs of G.
2. It is evident that every (nontrivial) graph G consists of one or more connected graphs. Each connected graph is a subgraph of G
and is called a component of G.
3. Obviously, a connected graph has only one component and a disconnected graph has two or more [Link] number of
components of a graph G is denoted by 𝑘 𝐺 .

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Euler Trails and Circuits

Euler circuits and Euler trails

Consider a connected graph G. if there is circuit in G that contains all the edges of G, then
that circuit is called an Euler circuit (or Euclerian 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
in G.

A connected graph that contains an Euler circuit is called an Euler Graph (or Euclearian
graph).
A connected graph that contains an Euler trail is called an semi-Euler Graph (or Euclearian
graph).

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Euler Trails and Circuits

Example:

Closed walk 𝑃𝑒1 𝑄𝑒2 𝑅𝑒3 𝑃𝑒4 𝑆𝑒5 𝑇𝑒7 𝑃

It is a Euler [Link] the graph is Euler graph

Open walk 𝐴𝑒1 𝐵𝑒2 𝐷𝑒3 𝐶𝑒4 𝐴𝑒5 𝐷

It is an Euler trail, it is an semi Euler graph.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Vertex degree: Euler Trails and Circuits

Theorem: 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:
Suppose that G has an Euler circuit. While tracing this circuit we observe that every time the
circuit meets a vertex 𝑣 it goes through two edges incident on 𝑣.
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.

Therefore, the degree of every vertex is a multiple of two

That is every vertex is of even degree.
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Hamilton cycles and Hamilton paths

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.

 A Hamilton cycle (when it exists) in a graph of n vertices consists of exactly n edges. Because, a cycle

with n vertices has n edges.

 By definition, a Hamilton cycle (when it exists) in a graph G must include all vertices is G. This does not

mean that it should include all edges of G.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Hamilton cycles and Hamilton paths

A graph that contains a Hamilton cycle is called Hamilton graph (or Hamiltonian graph).
For example, in the graph shown in figure 10.1 the cycle shows in thick lines is a Hamilton
cycle. (Observe that this cycle does not include the edge BD). The graph is therefore a
Hamilton graph.

A path (if any) in a connected graph which includes every vertex (but not necessarily every edge) of the
graph is called a Hamilton Path (Hamiltonian path) in the graph. For example, in the graph shown in
figure 10.2, the path shown in thick lines is a Hamilton path.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Hamilton cycles and Hamilton paths

1. Show that the graph shown below is an Euler graph 2. Find an Euler circuit in the graph shown below

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Hamilton cycles and Hamilton paths

3. Show that the following graph does not contain an Euler circuit. 4. Show that the following graph contains an Euler trail

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Hamilton cycles and Hamilton paths

(Dirac’s Theorem) 1: If in a simple connected graph with 𝑛 vertices (where 𝑛 ≥ 3) the

sum of the degrees of every pair of non-adjacent vertices is greater than equal to 𝑛, then the
graph is Hamiltonian.

Theorem 2: If in a simple connected graph with 𝑛 vertices (where 𝑛 ≥ 3) the degree of

every vertex is greater than equal to 𝑛/2, then the graph is Hamiltonian.

Note:
Complete graph 𝐾𝑛 , where 𝑛 ≥ 3, is a Hamiltonian graph.
Every simple k-regular graph with 2𝑘 − 1 vertices is a Hamiltonian graph

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Hamilton cycles and Hamilton paths

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
 3. Show that the following graphs do not have Hamiltonian
1. Identify five different Hamilton cycles in the paths and Hamiltonian cycles.
following graph

4. Show that the following graphs are Hamiltonian but not

Eulerian.

2. Show that the following graphs are Hamiltonian

graphs.

5. Which of the following are Euler graphs? Hamilton graphs?

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

Planar graphs and coloring

In this chapter, we present an elementary discussion on planar and non-planar graphs. The so-called dual
graphs associated with planar graphs are also defined and illustrated. The problem of graph coloring is briefly
dealt-with.

A graph can be represented by more than one geometrical drawing. In some drawings representing graphs, the
edges intersect (cross over) at points which are not vertices of the graph and in some others the edges meet only
at the vertices.

A graph which can be represented by at least one plane drawing (drawing done on a plane surface) in which the
edges meet only at the vertices is called a planar graph.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

On the other hand, a graph which cannot be represented by a plane drawing in which the edges meet only at the

vertices is called a non-planar graph.

In other words, a non-planar graph whose every possible plane drawing contains at least two edges which intersect

each other at points other than vertices.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Planar Graphs

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

Euler’s formula
If G is a planar graph, then G can be represented by a diagram in a plane in which the edges meet only at the vertices.

Such a diagram divides the plane into a number of parts, called regions (or faces), of which exactly one part is

unbounded. The number of edges that form the boundary of a region is called the degree of that region.

For example in the diagram of a planar graph shown in below Figure, the diagram divides the plane into 6 regions R1,

R2, R3, R4, R5, R6. We observe that each of the regions R1 to R5 is bounded and the region R6 is unbounded. We say

that the regions R1 to R5 are in the interior of the graph and the region R6 is in the exterior.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

𝑑 𝑅1 = 2
𝑑 𝑅2 = 3
𝑑 𝑅3 = 5
𝑑 𝑅4 = 3
𝑑 𝑅5 = 1
𝑑 𝑅6 = 6 and
𝑑 𝑅1 + 𝑑 𝑅2 + 𝑑 𝑅3 + 𝑑 𝑅4 + 𝑑 𝑅5 + 𝑑 𝑅6 = 20
The twice the number of edges in the graph. This property is analogous to the handshaking property and true for all
planar graphs.

Theorem: A connected planar graph G with 𝑛 vertices and 𝑚 edges has exactly 𝑚 − 𝑛 + 2 regions in all of its diagram.
That is 𝑟 = 𝑚 − 𝑛 + 2 or 𝑛 − 𝑚 + 𝑟 = 2

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

NOTE:

1. If G is a connected, simple planar graph with 𝑛 (≥ 3) vertices, 𝑚(> 2) edges and 𝑟

3
regions then, 𝑖. 𝑚 ≥ 𝑟, 𝑖𝑖. 𝑚 ≤ 3𝑛 − 6
2

2. Kuratowski’s first graph, is non planar

3. Kuratowski’s second graph, is non planar

4. Every connected simple planar graph G contains a vertex of degree less than 6.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs
[Link] the diagram of a graph shown below verify Euler's formula.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs
[Link] Euler’s formula for the planar graphs shown below.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs
3. A connected planar graph G has 9 vertices with degrees 2, 2, 3, 3, 3, 4, 5, 6, 6. Find the
number of regions of G.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

Detection of planarity
Given a graph G, the determination of its planarity or otherwise is an important problem. This problem can be

tackled by employing what is known as Elementary Reduction. The steps involved in this reduction are as explained

below:

Elementary Reduction

Step 1. Given a graph G, determine the set

𝐴 = 𝐺1 , 𝐺2 , … … … … . . 𝐺𝑘

Where 𝐺1 , 𝐺2 , … … … … . . 𝐺𝑘 are subgraphs of G every pair of which has exactly one vertex in common (-such subgraphs are

called blocks).

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

Step 2. Remove all loops from all of 𝐺𝑖 𝑠.

Step 3. Remove all but one edge between every pair of vertices joined by multiple edges (if any).

Step 4. Eliminate all vertices of degree 2 by merging the edges incident on these vertices.

Step 5. Repeat the steps 3 and 4 repeatedly until each block 𝐺𝑖 is reduced to a new graph 𝐻𝑖 which will be one of the following.

(1) A graph with a single edge.

(2) A complete graph of order four.

If 𝐻𝑖 is in the first or second of the above possible forms, we conclude that 𝐻𝑖 is a planar graph. Consequently, each 𝐺𝑖 with

which we started is planar and therefore 𝐺 is planar.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

Example 1: Carry out the elementary reduction process for the following graph shown in below Figure.

Step 1 : The given graph 𝐺 is a single block. Therefore, the set 𝐴 of step 1 contains only 𝐺.

Step 2 : we have to remove the loops. In the graph, there is one loop consisting of the edge 𝑒9 . Let us remove it.

Step 3: we have to remove one of the two parallel edges from each vertex pair having such edges. In the given graph,
𝑒1 , 𝑒8 are parallel edges. Let us remove 𝑒8 from the graph. The graph left-out after the first three steps is as shown
below:

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

Step 4: we have to eliminate the vertices of degree 2 by merging the edges incident on these vertices. Thus, we
merge (i) the edges, e1 and e2 into an edge, e10 (say) and (ii) the edges , e6 and e7 into an edge e11 (say). The
resulting graph will be shown below.

As per Step 3, let us remove one of the parallel edges 𝑒5 and 𝑒10 and one of the parallel edges 𝑒3 and 𝑒11 . The graph
got be removing 𝑒10 and 𝑒11 will be as shown below:

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs
As per step 4, we merge the edges 𝑒3 and 𝑒4 into an edge 𝑒12 (say) to get the following graph.

As per step 3, we remove one of the two parallel edges, say 𝑒12. Thus, we get the following graph.

This graph is final graph obtained by the process of elementary reduction applied to the given graph

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs
Example 2: Check the planarity (or otherwise) of the following graph by the method of elementary reduction.

Solution: The elementary reduction of the given graph 𝐺 consists of the following steps:
Step 1: splitting 𝐺 into blocks. This splitting is shown below:

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

Step 2: Removing loops and eliminating multiple edges. The resulting graph is as shown below:

Step 3: Merging the edges incident on vertices of degree 2. The resulting graph is as shown below:

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

Step 4: Eliminating parallel edges. The resulting graph is as shown below:

The reduction is now complete. The final reduced graph (shown in figure) has three blocks, of which the first and the
third (which are single edges) are obviously planar. The second one is the complete graph, 𝐾5 , which is non-planar.
Thus, the given graph contains 𝐾5 as a subgraph and is therefore non-planar.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

Dual of a planar graph

 Consider a connected planar graph 𝐺 and a plane drawing thereof. Suppose 𝑅1 , 𝑅2 , 𝑅3 , 𝑒𝑡𝑐. , are the regions

(including the exterior region) in this drawing. Let us now construct a graph 𝐺 ∗ using the procedure given

below:

1. Choose one point inside each of the regions 𝑅1 , 𝑅2 , 𝑅3 ,…… Denote these points by 𝜐1∗ , 𝜐2∗ , 𝜐3∗ , … , respectively.

2. If two regions 𝑅𝑖 and 𝑅𝑗 are adjacent (i.e. have a common edge, say 𝑒𝑘 ), draw a line 𝑒𝑘∗ joining the points 𝜐𝑖∗

and 𝜐𝑗∗ that intersects the common edge 𝑒𝑘 exactly once.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

1. If there is more than one edge common to 𝑅𝑖 and 𝑅𝑗 , draw one line 𝑒𝑝∗ between the points 𝜐𝑖∗ and 𝜐𝑗∗ for each

common edge 𝑒𝑝 , interesting 𝑒𝑝 exactly once.

2. For an edge 𝑒𝑖 , lying entirely in one region, say 𝑅𝑖 , draw a loop 𝑒𝑖∗ at the point 𝜐𝑖∗ intersecting 𝑒𝑖 exactly once.

The graph 𝐺 ∗ for which 𝜐𝑖∗ are vertices and 𝑒𝑖∗ are edges constructed as explained above is called the geometric

dual or just the dual of 𝐺.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs

For example, consider the connected planar graph 𝐺 a plane drawing of which is shown in Figure 2.31. we observe
that the drawing divides the plane into regions 𝑅1 , 𝑅2 , 𝑎𝑛𝑑 𝑅3 , Of which 𝑅3 is unbounded. We construct the dual
𝐺 ∗ of 𝐺 by using the afore- stated procedure. The step-by-step description of the construction is given below.

We choose three points 𝜐1∗ , 𝜐2∗ , 𝜐3∗ inside the regions 𝑅1 , 𝑅2 , 𝑅3 , respectively.

The regions 𝑅1 , 𝑎𝑛𝑑 𝑅2 have a common edge 𝑒5 . We draw a line 𝑒5∗ joining 𝜐1∗ , 𝑎𝑛𝑑 𝜐2∗ that cross 𝑒5
exactly once.

The regions 𝑅1 𝑎𝑛𝑑 𝑅3 have two common edges 𝑒1 , 𝑒2 . We draw two lines 𝑒1∗ , 𝑒2∗ between 𝜐1∗ , 𝑎𝑛𝑑 𝜐3∗ ,
with 𝑒1∗ crossing only 𝑒1 and 𝑒2∗ crossing only 𝑒2 .

The regions 𝑅2 𝑎𝑛𝑑 𝑅3 have two common edges 𝑒3 , 𝑒4 . We draw two lines 𝑒3∗ , 𝑒4∗ between
𝜐2∗ , 𝑎𝑛𝑑 𝜐3∗ , with 𝑒3∗ crossing only 𝑒3 and 𝑒4∗ crossing only 𝑒4 .

The edge 𝑒6 is completely contained in 𝑅3 . We draw a loop 𝑒6∗ at 𝜐3∗ interesting 𝑒6 exactly once.

The construction of 𝐺 ∗ is now complete. For 𝐺 ∗ , the points 𝜐1∗ , 𝜐2∗ , 𝜐3∗ , are the vertices and
these lines 𝑒1∗ , 𝑒2∗ , 𝑒3∗ , 𝑒4∗ , 𝑒5∗ , 𝑎𝑛𝑑 𝑒6∗ are the edges.
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Planar Graphs

Some results

The results listed below follow from the procedure used in the construction of 𝐺 ∗ :

1. There is a one-to-one correspondence between the regions of 𝐺 and the vertices of 𝐺 ∗ .

2. There is a one-to-one correspondence between the edges of 𝐺 and the edges of 𝐺 ∗ . (if 𝑒 ∗ is the edge of 𝐺 ∗ that corresponds to the edge

3. The pendant edge in G yields a loop in 𝐺 ∗ .

4. A loop in G yields a pendant edge in 𝐺 ∗ .

5. Edges that are in series in G yield parallel edges in 𝐺 ∗ .

6. Parallel edges in G yield edges in series in 𝐺 ∗

7. The number of edges which form a boundary of a Region 𝑅𝑖 in G is equal to the degree of the corresponding vertex 𝜐𝑖∗ in 𝐺 ∗ , and vice-

versa.

8. Like G, 𝐺 ∗ is a connected planar graph.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Planar Graphs
1. Check the planarity of the following graph by elementary reduction
3.

2.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Colouring

Graph Colouring
Example: Suppose we want to make an exam schedule for a university. We have list of different subjects and

students enrolled in every subject. Many subjects would have common students (of same batch, some backlog

students, etc). How do we schedule the exam so that no two exams with a common student are scheduled at

same time? How many minimum time slots are needed to schedule all exams? (vertex represents subject and

edge represents common students)

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Colouring

Graph Colouring
Given a planar or non-planar graph G, if we assign colours to its vertices in such a way that no two
adjacent vertices have the same colour, then we say that the graph G is properly coloured.

In other words, proper colouring of a graph means assigning colours to its vertices such that adjacent vertices
have different colours.

Note:
1. A graph can have more than one proper
colouring
2. Two non adjacent vertices in a properly coloured
graph can have the same colour.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Colouring

Chromatic Number
A graph G is said to be 𝑘 − 𝑐𝑜𝑙𝑜𝑢𝑟𝑎𝑏𝑙𝑒 if we can properly colour it with 𝑘(number of) colours.

A graph G is 𝑘 − 𝑐𝑜𝑙𝑜𝑢𝑟𝑎𝑏𝑙𝑒 but not 𝑘 − 1-𝑐𝑜𝑙𝑜𝑢𝑟𝑎𝑏𝑙𝑒 is called a 𝑘 − 𝑐ℎ𝑟𝑜𝑚𝑎𝑡𝑖𝑐 graph.

In other words, a 𝑘 − 𝑐ℎ𝑟𝑜𝑚𝑎𝑡𝑖𝑐 graph is a graph that can be properly coloured with 𝑘 colours
but not with less than k colours.

If graph G is 𝑘 − 𝑐ℎ𝑟𝑜𝑚𝑎𝑡𝑖𝑐, then 𝑘 is called chromatic number.

The chromatic number of a graph G is usually denoted by 𝝌(𝑮).

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Colouring

Some results:
1. The graph consists of only isolated vertex is 1-chromatic (Null graph)

2. A graph with one or more edges is at least 2-chroamatic.

3. If a graph G contains a graph 𝐺1 as a subgraph, then𝝌(𝑮) ≥ 𝝌(𝑮𝟏 )

4. If G is a graph on 𝑛 vertices, then 𝝌(𝑮) ≤ 𝒏.

5. The chromatic number of the complete graph 𝑘𝑛 is n that is 𝝌 𝑘𝑛 = 𝒏.

6. If a graph G contains 𝑘𝑛 as subgraph, then 𝝌(𝑮) ≥ 𝒏.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Colouring
1. Find the chromatic number of each of the following graphs.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Colouring

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Colouring

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Graph Colouring

Coloring a Wheel
A graph of this form is called a wheel.

In wheels with an even number of “spokes”, you can alternate colors on the outside,
then add an additional color for the center vertex. As is seen in this wheel with 6
spokes, a wheel with an even number of spokes can be 3-colored.

 (G ) = 3

In wheels with an odd number of spokes, it’s not possible to alternate

colors on the outside, so there must be 3 colors on the outside and
then an additional color for the center vertex, thus the chromatic
number is 4.
 (G ) = 4
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Chromatic Polynomial

Chromatic Polynomial:
The number of different ways of properly colouring graph 𝐺 with 𝜆 number of colours is denoted
by 𝑃(𝐺, 𝜆). Then we have the following
 𝑃 𝑁𝑛 , 𝜆 = 𝜆𝑛 where 𝑁𝑛 represents null graph with n vertices.
 𝑃 𝐾𝑛 , 𝜆 = 0 𝑖𝑓 𝜆 < 𝑛,
 𝑃 𝐾𝑛 , 𝜆 = 1 𝑖𝑓 𝜆 = 𝑛
 𝑃 𝐾𝑛 , 𝜆 = 𝜆 𝜆 − 1 𝜆 − 2 ⋯ 𝜆 − 𝑛 + 1 𝑖𝑓 𝜆 > 𝑛 where 𝐾𝑛 Represents complete
graph.
 𝑃 𝐿𝑛 , 𝜆 = 𝜆 𝜆 − 1 𝑛−1 𝑖𝑓 𝜆 ≥ 2
We observe that in each of above cases, 𝑃(𝐺, 𝜆) is a polynomial. This polynomial is called
Chromatics polynomial.
The chromatic polynomial 𝑃(𝐺, 𝜆) of a graph 𝐺 represents the number of ways of properly
colouring 𝐺 with 𝜆 number of colours.

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial

If a graph 𝐺 is made up of 𝑛 parts 𝐺1 , 𝐺2 , … , 𝐺𝑛 then 𝑃(𝐺, 𝜆) is given by the following Product Rule

𝑷 𝑮, 𝝀 = 𝑷 𝑮𝟏 , 𝝀 ⋅ 𝑷 𝑮𝟐 , 𝝀 ⋯ 𝑷(𝑮𝒏 , 𝝀)
In particular, if 𝐺 is made up of two parts 𝐺1 and 𝐺2 , then we have

𝑷 𝑮, 𝝀 = 𝑷 𝑮𝟏 , 𝝀 ⋅ 𝑷 𝑮𝟐 , 𝝀
𝑷 𝑮, 𝝀
𝑷 𝑮𝟐 , 𝝀 =
𝑷 𝑮𝟏 , 𝝀

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial

1. Mobile Radio Frequency Assignment: When frequencies are assigned to towers, frequencies assigned to all
towers at the same location must be different. How to assign frequencies with this constraint? What is the
minimum number of frequencies needed? This problem is also an instance of graph coloring problem where
every tower represents a vertex and an edge between two towers represents that they are in range of each other.

2. Sudoku: Sudoku is also a variation of Graph coloring problem where every cell represents a vertex. There is an
edge between two vertices if they are in same row or same column or same block.

3. Register Allocation: In compiler optimization, register allocation is the process of assigning a large number of
target program variables onto a small number of CPU registers. This problem is also a graph coloring problem.

4. Bipartite Graphs: We can check if a graph is Bipartite or not by coloring the graph using two colors. If a given
graph is 2-colorable, then it is Bipartite, otherwise not. See this for more details.

5. Map Coloring: Geographical maps of countries or states where no two adjacent cities cannot be assigned same
color. Four colors are sufficient to color any map (See Four Color Theorem)

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial

DECOMPOSITION THEOREM:
Let 𝐺 be a graph and 𝑒 = {𝑎, 𝑏} be an edge of 𝐺. Let 𝐺𝑒 = 𝐺 – 𝑒 be that subgraph of 𝐺 which is obtained by deleting
𝑒 from 𝐺 without deleting vertices 𝑎 and 𝑏. Suppose we construct a new graph 𝐺𝑒‘ by coalescing (identifying /
merging) the vertices 𝑎 and 𝑏 in 𝐺𝑒 . Then 𝐺𝑒‘ is subgraph of 𝐺𝑒 as well as 𝐺.
The process of obtaining 𝐺𝑒 and 𝐺𝑒‘ from 𝐺. And is illustrated in Figure

The following theorem called the Decomposition

theorem for chromatic polynomials given an expression for 𝑃 (𝐺, 𝜆) in terms of 𝑃 (𝐺𝑒, 𝜆) and 𝑃 (𝐺𝑒‘, 𝜆) for a
connected graph 𝐺.

Theorem 1: If 𝐺 is a connected graph and 𝑒 = {𝑎, 𝑏} is an edge of 𝐺, then

𝑃 (𝐺𝑒, 𝜆) = 𝑃 (𝐺, 𝜆) + 𝑃 (𝐺𝑒‘, 𝜆)

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial

MULTIPLICATION THEOREM
The following theorem gives an expression for 𝑃(𝐺, 𝜆) for a special class of
graphs.
Theorem 2: If a graph 𝐺 has sub graphs 𝐺1 and 𝐺2 such that 𝐺1 ∪ 𝐺2 =
𝐺 and 𝐺1 ∩ 𝐺2 = 𝐾𝑛 for some positive integer n, then

𝑃 𝐺1 , 𝜆 . 𝑃 𝐺2 , 𝜆
𝑃 𝐺, 𝜆 =
𝜆𝑛

Where 𝜆𝑛 = 𝜆 (𝜆 − 1)( 𝜆 − 2) … (𝜆 – 𝑛 + 1)

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial

1. Find the chromatics polynomial for the following graph

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial

Problems
1. Consider the graph K2,3 shown in Figure .Let 𝜆 denote the number of colors
available to properly color the vertices of this graph. Find:
1. how many proper colorings of the graph have vertices 𝑎, 𝑏 colored the same.
2. how many proper colorings of the graph have vertices 𝑎, 𝑏 colored with different
colors.
3. The chromatic polynomial of the graph.
4. For the graph 𝐾2, 𝑛 what is the chromatic polynomial?

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial
(i) If the vertices 𝑎 and 𝑏 are to have the same color, then there are 𝜆 choices for coloring the vertex 𝑎 and
only one choice for the vertex 𝑏 (or vice versa). Consequently, there are 𝜆– 1 choices for each of the
vertices 𝑥, 𝑦, 𝑧. Hence, the number of proper colorings (in this case) is 𝜆 (𝜆 − 1)3
(ii) If the vertices 𝑎 and 𝑏 are to have different colors, then there are 𝜆 choices for coloring the vertex 𝑎 and
𝜆 − 1 choices for the vertex 𝑏 (or vice versa). Consequently, there are 𝜆– 2 choices for each of the vertices
𝑥, 𝑦, 𝑧. Hence the number of proper colorings (in this case) is 𝜆 (𝜆 − 1) (𝜆 − 2)𝟑.
(iii) Since the two cases of the vertices 𝑎 and 𝑏 have the same color or different colors are exhaustive and
mutually exclusive, the chromatic polynomial of the graph is
 𝑃(𝐾2 3, 𝜆) = 𝜆 (𝜆 − 1)𝟑 + 𝜆(𝜆 − 1)(𝜆 − 2)𝟑.
,

(iv) Let 𝑉1 = {𝑎, 𝑏} and 𝑉2 = {𝑥1, 𝑥2, 𝑥3, … … … 𝑥𝑛} be the two bipartite of 𝐾2 𝑛. Then, if 𝑎 and 𝑏 are to have
,
the same color, the number of proper colorings of 𝐾2, 𝑛 is 𝜆 (𝜆 − 1)𝒏 as in case (i) above, If 𝑎 and 𝑏 are to
have different colors, the number of proper colorings is
 𝜆 𝜆 − 1 𝜆 − 2 𝒏,as in case (ii) above. Consequently, the chromatic polynomial for 𝐾2, 𝑛 is

 𝑃(𝐾2 𝑛, 𝜆) = 𝜆 (𝜆 − 1)𝒏 + 𝜆(𝜆 − 1) (𝜆 − 2)𝒏 .

,

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial

2. Find the chromatic polynomial for the cycle 𝐶4 of length 4

A cycle of length 4, namely 𝐶4, is shown in Figure.

Let us redesignate it as 𝐺 and denote the edge {𝑣2, 𝑣3} as
𝑒. Then the graph 𝐺𝑒 and 𝐺𝑒‘ would be as shown below..

We note that the graph 𝐺𝑒 is a path with 4 vertices.

Therefore, 𝑃(𝐺𝑒, 𝜆) = 𝜆 (𝜆 − 1)3 Also, the graph 𝐺𝑒‘ is the
graph 𝐾𝟑 Therefore 𝑃(𝐺𝑒‘, 𝜆) = 𝜆(𝜆 − 1)(𝜆 − 2) Accordingly,
using the decomposition theorem, we find that
𝑃(𝐶4, 𝜆) = 𝑃(𝐺, 𝜆) = 𝑃(𝐺𝑒, 𝜆) − 𝑃(𝐺𝑒‘, 𝜆)
= 𝜆 (𝜆 − 1)𝟑 − 𝜆 (𝜆 − 1) (𝜆 − 2)
= 𝜆𝟒 – 4 𝜆𝟑 + 6 𝜆𝟐 − 3 𝜆 .
This is the chromatic polynomial for the given cycle.
DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
Chromatic Polynomial
3. Find the chromatic polynomial for the graph shown below. If 5 colors are available, in
how many ways can the vertices of this graph be properly colored?.
Let us denote the given graph by 𝐺 and the edge {𝑣1, 𝑣2} by 𝑒. Then the graph 𝐺𝑒 and
𝐺𝑒‘ would be as shown in Figure below

Let us redesignate the graph 𝐺𝑒 as 𝐻 and denote the edge {𝑣1, 𝑣5} as 𝑓. Then the graph 𝐻𝑓 and 𝐻′𝑓 would
appear as shown below:

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023

Chromatic Polynomial
Applying the decomposition theorem to the graphs 𝐺 and 𝐻 we note that
𝑃 𝐺, 𝜆 = 𝑃 𝐺𝑒, 𝜆 − 𝑃 𝐺𝑒‘, 𝜆 = 𝑃 𝐻, 𝜆 − 𝑃 𝐺𝑒‘, 𝜆
= 𝑃 𝐻𝑓 , 𝜆 − 𝑃 𝐻𝑓‘, 𝜆 − 𝑃 𝐺𝑒‘, 𝜆 −−− −(1)

We observe that both of the graphs 𝐺𝑒‘ and 𝐻𝑓‘ are the graph 𝐾4 and the graph 𝐻𝑓 is a disconnected graph having
𝑁1 (- null graph of order 1 consisting of the single vertex 𝑣1) and 𝐾4 as components. Accordingly,
𝑃 𝐺𝑒‘, 𝜆 = 𝑃 𝐻′𝑓 𝜆 = 𝑃 𝐾4, 𝜆 = 𝜆 𝜆 − 1 𝜆 − 2 𝜆 − 3 .
𝑃(𝐻𝑓 , 𝜆) = 𝑃(𝑁1, 𝜆) . 𝑃(𝐾4, 𝜆) = 𝜆. 𝜆 (𝜆 − 1) (𝜆 − 2) (𝜆 − 3).

Consequently, expression (i) gives

𝑃(𝐺, 𝜆) = 𝜆. 𝜆 (𝜆 − 1) (𝜆 − 2) (𝜆 − 3) − 2 𝜆(𝜆 − 1) (𝜆 − 2) (𝜆 − 3)
= 𝜆 (𝜆 − 1) (𝜆 − 2) (𝜆 − 3) (𝜆 − 2)
= 𝜆 (𝜆 − 1) (𝜆 − 2)𝟐 (𝜆 − 3).

This is the chromatic polynomial for the given graph. For λ = 5, this polynomial gives
𝑃(𝐺, 𝜆) = 5 𝑥 4 𝑥 32 𝑥 2 = 360.

This means DISCRETE

that if 5 MATHEMATICS & GRAPH THEORY
colors are available, the vertices of the graph can be properly colored in 360 different ways. 3/29/2023
 Chromatic Polynomial
4. Use the multiplication theorem to find P(G, λ) for the graph shown in Figure.

The graph G in figure can be regarded as the union of the graphs G1 and G2 shown in
figures below

Then G1∩ G2 = {v5,v2}Shown in Figure (c).

We note that G1 is the same as K3,G2 is the same as K4 and G1∩G2 is the same as K2. Hence, using the
multiplication theorem (Theorem 2), we get
P (G, λ) = P (G1, λ) . P (G2, λ) / λ(2) = P (K3, λ) . P (K4, λ) / λ(2)

= λ (λ-1) (λ-2) . λ(λ-1) (λ-2) (λ-3) / λ (λ-1)

= λ (λ-1) (λ-2)2 (λ-3)

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023
As the chromatic polynomial for the give G
Chromatic Polynomial

DISCRETE MATHEMATICS & GRAPH THEORY 3/29/2023