GRAPH THEORY (BCS405B) 2024

MODULE-2

Eulerian and Hamiltonian graphs: Euler graphs, Operations on graphs, Hamiltonian paths and circuits, travelling
salesman problem. Directed graphs – types of digraphs, Digraphs and binary relation.
Lecture 1: 𝐄𝐮𝐥𝐞𝐫 𝐥𝐢𝐧𝐞 𝐚𝐧𝐝 𝐄𝐮𝐥𝐞𝐫 𝐠𝐫𝐚𝐩𝐡.
𝐄𝐮𝐥𝐞𝐫 𝐥𝐢𝐧𝐞 𝐚𝐧𝐝 𝐄𝐮𝐥𝐞𝐫 𝐠𝐫𝐚𝐩𝐡:
Let G( V, E ) be an undirected graph or multigraph with no isolated vertices.
Closed walk containing all the edges of the graph is called 𝐄𝐮𝐥𝐞𝐫 𝐥𝐢𝐧𝐞 and the graph is called Euler graph.

Example: 𝑐
𝑏 2
1 3
7 8
𝑎 9 10 𝑑
6 4
𝑓 5 𝑒

Given graph is Euler graph. Clearly a closed walk "𝑎1𝑏2𝑐3𝑑4𝑒7𝑏9𝑓8𝑐10𝑒5𝑓6𝑎" contains all the edges exactly
once and hence this is one of the Euler lines.
Some other Euler lines are "𝑎1𝑏9𝑓8𝑐2𝑏7𝑒10𝑐3𝑑4𝑒5𝑓6𝑎" , "𝑏1𝑎6𝑓9𝑏2𝑐3𝑑4𝑒10𝑐8𝑓5𝑒7𝑏" ,
"𝑑3𝑐2𝑏1𝑎6𝑓9𝑏7𝑒5𝑓8𝑐10𝑒4𝑑".
In each of the closed walk given above all the edges are appears only once and hence they are Euler line.

Unicursal line and unicursal graph: An open walk containing all the edges of the graph is called an unicursal
line or an open Euler line and the graph is called unicursal graph.
Example:
𝑏 𝑐
2
3
1
7 8
𝑎 9 𝑑

6 4
𝑓 5 𝑒

In the above graph, "𝑐2𝑏1𝑎6𝑓9𝑏7𝑒5𝑓83𝑑4𝑒" is an open walk containing all the edges, and hence it is
unicursal line. Therefore, graph is unicursal graph.
Some other unicursal lines are "𝑐3𝑑4𝑒7𝑏2𝑐8𝑓9𝑏1𝑎6𝑓5𝑒" , "𝑒5𝑓6𝑎1𝑏9𝑓8𝑐2𝑏7𝑒4𝑑3𝑐" .
Euler line in a graph is nothing but a solution to trace a graph starting from a vertex go through each edge
exactly once without lifting the pen and reach the starting point.
Similarly, unicursal line is tracing of graph without lifting the pen starting from a vertex go through each edge
exactly once and reach another vertex.

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

1
GRAPH THEORY (BCS405B) 2024

Review questions:

1. Is the Eulerian graph having unique Euler line?

2. Is the Unicursal graph having unique Unicursal line?
3. In what condition a graph has Euler line?
4. In what condition a graph has Unicursal line?
5. For what values of n , K 𝑛 has a Euler line?

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

2
GRAPH THEORY (BCS405B) 2024

Lecture 2: 𝐄𝐮𝐥𝐞𝐫 𝐥𝐢𝐧𝐞 𝐚𝐧𝐝 𝐄𝐮𝐥𝐞𝐫 𝐠𝐫𝐚𝐩𝐡.

Theorem: A given connected graph G is a Euler graph if and only if all the vertices of G are of even degree.
Proof: If 𝐺 is a Euler graph, then 𝐺 contains a Euler line. Let 𝑎 be the starting vertex of the Euler line. In tracing
this walk for any vertex 𝑣 of 𝐺, each time the walk comes to 𝑣 it then departs from the vertex 𝑣. Thus the walk
has traversed either two new edges that are incident with 𝑣 or a new loop at 𝑣. In either case a count of 2 is
contributed to deg (𝑣). Since 𝑣 is not the starting vertex a count of 2 is obtained each time the circuit passes
through 𝑣, so degree of 𝑣 is even. For the starting vertex 𝑎, the first edge of the circuit must be distinct from
the last edge, and any other visit to a result in a count of 2 for deg (𝑎), we have deg (𝑎) is also even.
Conversely, let G be a connected graph with every vertex of even degree. If the number of edges in G is 1 or 2,
then G is of the forms

Euler line is immediate in these cases. We proceed now by induction and assume the result true for all
situations where there are fewer than 𝑛 edges. If G has n edges, select a vertex 𝑎 in G as a starting point to
build a Euler line. The graph G is connected and each vertex is of even degree, so we can construct a closed
walk C containing 𝑎. If this closed walk contains every edge of G, we are finished. If not, remove the edges of C
from G and any vertex that would become isolated. The remaining subgraph 𝐾 has all vertices of even degree,
but it may not be connected. However, each component of 𝐾 is connected and by induction hypotheses will
have a Euler line. In addition, each of these Euler line has a vertex that is on C. Consequently, starting from 𝑎
we travel on C until we arrive at a vertex 𝑣1 that is on the Euler line 𝐶1 of the component of 𝐾. Then we
traverse this Euler line and returning to 𝑣1 , continue on C until we reach a vertex 𝑣2 that is on the Euler line 𝐶2
of another component of K. Since the graph is finite, as continue this process we construct an Euler line for G.

Theorem: A given connected graph is unicursal graph if and only if it has exactly two vertices of odd degree.
Proof: If a graph G has unicursal line. Let 𝑎 be the starting vertex and 𝑏 be the end vertex of the unicursal line.
In tracing this walk for any vertex 𝑣 of 𝐺, each time the walk comes to 𝑣 it then departs from the vertex 𝑣.
Thus, the walk has traversed either two new edges that are incident with 𝑣 or a new loop at 𝑣. In either case a
count of 2 is contributed to deg (𝑣). Since 𝑣 is not the starting vertex a count of 2 is obtained each time, the
walk passes through 𝑣, so degree of 𝑣 is even. For the starting and end vertices are distinct and the first edge
of the circuit must be distinct from the last edge, and any other visit to a result in a count of 2 for deg (𝑎) and
deg (𝑏), we have deg (𝑎) and deg (𝑏) are odd.
Conversely, if 𝐺 is connected graph and 𝑎 and 𝑏 are the vertices of 𝐺 that have odd degree. Add an edge
{𝑎, 𝑏}between 𝑎 and 𝑏 to 𝐺, we get 𝐺1 . Clearly the graph 𝐺1 is connected and has every vertex of even degree.
Hence 𝐺1 has a Euler line 𝐶, and when the edge {𝑎, 𝑏} is removed from 𝐶, we obtain an open Euler line for 𝐺
that is unicursal line.

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

3
GRAPH THEORY (BCS405B) 2024

1. You are given a 10-piece domino set whose titles have the following set of dots: (1, 2); (1, 3); (1, 4);
(1, 5); (2, 3); (2, 4); (2, 5); (3, 4); (3, 5); (4, 5). Discuss the possibility of arranging the tiles in a
connected series such that one number on a title always touches the same number on its neighbor.
Solution: Consider the complete graph 𝐾5 .
2

1 3

4
5
Clearly 𝐾5 has Euler line. "1 − 2 − 3 − 4 − 5 − 2 − 4 − 1 − 3 − 5 − 1".
Since 1 is neighbor of 2, 3, 4, 5. 2 is neighbor of 1, 3, 4, 5. 3 is neighbor of 2, 4, 1, 5. 4 is neighbor of 1,
2, 3, 4. And 5 is neighbor of 1, 2, 3,4 we can arrange the tiles in a connected series such that one number
on a title always touches the same number on its neighbor.

Review questions:
1. How to check the given graph is Eulerian?
2. How to check the given graph is Unicursal?
3. Is there Euler graph containing unicursal line?
4. Is there a graph contains unicursal line but not Euler line?
5. Whether a Euler graph contains a self-loop?
6. Whether a Euler graph contains parallel edges?

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

4
GRAPH THEORY (BCS405B) 2024

Lecture 3: Operations on graph.

Operations on graph: Let 𝐺1 (𝑉1 , 𝐸1 ) and 𝐺2 (𝑉2 , 𝐸2 ) are given two graphs.
Union of two graphs: 𝐺1 ∪ 𝐺2 = 𝐺3 (𝑉3 , 𝐸3 ), where 𝑉3 = 𝑉1 ∪ 𝑉2 and 𝐸3 = 𝐸1 ∪ 𝐸2 .
Intersection of two graphs: 𝐺1 ∩ 𝐺2 = 𝐺4 (𝑉4 , 𝐸4 ), where 𝑉4 = 𝑉1 ∩ 𝑉2 and 𝐸4 = 𝐸1 ∩ 𝐸2 .
Ring sum of two graphs:
𝐺1 ⊕ 𝐺2 = 𝐺5 (𝑉5 , 𝐸5 ), where 𝑉5 = 𝑉1 ∪ 𝑉2 and 𝐸5 = 𝐸1 ⨁𝐸2 (i.e. edges that are in 𝐺1 or in 𝐺2 but not in both.
Clearly if 𝐺1 and 𝐺2 are edge disjoint, then 𝐺1 ∩ 𝐺2 is a null graph and 𝐺1 ∪ 𝐺2 = 𝐺1 ⊕ 𝐺2 .
If 𝐺1 and 𝐺2 are vertex disjoint, then 𝐺1 ∩ 𝐺2 is empy.
For any graph 𝐺, 𝐺 ∪ 𝐺 = 𝐺, 𝐺 ∩ 𝐺 = 𝐺 and 𝐺⨁𝐺 = Null graph.

If 𝐺1 is subgraph of 𝐺, then 𝐺 ⊕ 𝐺1 is a subgraph of 𝐺 obtained by removing all the edges of 𝐺1 from 𝐺.

Therefore, if 𝐺1 is subgraph of 𝐺 then 𝐺 ⊕ 𝐺1 = 𝐺 − 𝐺1 . (Compliment of 𝐺1 in 𝐺).

Find the union, intersection, and ring sum of the following two graphs.
𝑣1
𝑣1 ℎ 𝑣6
𝑎 𝑏
𝑎 𝑔
𝑣2 𝑣3 𝑘
𝑐
𝑙
𝑑 𝑒 𝑣2 𝑐 𝑣3

𝑣5
𝑣4 𝑓 𝑣5

𝐺2
𝐺1
𝑣1

ℎ
𝑎 𝑏
𝑔
𝑣3 𝑣6
𝐺1 ∪ 𝐺2 : 𝑣2 𝑘
𝑐

𝑑 𝑒 𝑙

𝑣4 𝑓 𝑣5

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

5
GRAPH THEORY (BCS405B) 2024

𝑣1

𝐺1 ∩ 𝐺2 : 𝑎

𝑣2 𝑣3
𝑐

𝑣5

𝑣1

𝐺1 ⊕ 𝐺2 : ℎ
𝑏
𝑔
𝑣3 𝑣6
𝑣2 𝑘

𝑑 𝑒 𝑙

𝑣4 𝑓 𝑣5

Review questions:
1. If 𝐺1 is subgraph of 𝐺2 , then 𝐺1 ∪ 𝐺2 ?
2. If 𝐺1 is subgraph of 𝐺2 , then 𝐺1 ∩ 𝐺2 ?
3. If 𝐺1 is subgraph of 𝐺2 , then 𝐺1 ⊕ 𝐺2 ?
4. If 𝐺1 and 𝐺2 are edge disjoint graphs, then 𝐺1 ⊕ 𝐺2 is?
5. If 𝐺 is simple graph containing 𝑛 vertices 𝐺 ⊕ 𝐾𝑛 = ?
6. If 𝐺 is simple graph containing 𝑛 vertices 𝐺 ∩ 𝐾𝑛 = ?
7. If 𝐺 is simple graph containing 𝑛 vertices 𝐺 ∪ 𝐾𝑛 = ?

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

6
GRAPH THEORY (BCS405B) 2024

Lecture 4: Operations on graph.

Decomposition: Two subgraphs 𝐺1 and 𝐺2 of a graph 𝐺 are said to be decomposition of 𝐺 if,

𝐺1 ∪ 𝐺2 = 𝐺 and 𝐺1 ∩ 𝐺2 = a null graph.

Deletion: Let 𝑣 be any vertex of a graph 𝐺, then 𝐺 − 𝑣 denotes a subgraph of 𝐺 obtained by deleting the vertex
𝑣 and all the edges incident on 𝑣 from 𝐺.

For any edge 𝑒 of 𝐺, 𝐺 − 𝑒 is a subgraph of 𝐺 obtained by deleting the edge 𝑒 only from 𝐺.
∴ 𝐺−𝑒 =𝐺⊕𝑒.

𝐺
𝑣

Graph 𝐺 − 𝑣 Graph 𝐺 − 𝑎.

Fusion: A pair of vertices 𝑎, 𝑏 in a graph are said to be fused (merged or identified) if the two vertices are
replaced by a single new vertex such that every edge that was incident on either 𝑎 or 𝑏 or on both is
incident on the new vertex.
𝑒
𝑒 𝑓 2
1 1
3
2 3
𝑓
𝑎 𝑏 (𝑎𝑏)
4
4 5 6
6 5

𝑑 𝑐 7 𝑑
𝑐 7
Given graph Fusion of vertices 𝑎 and 𝑏.

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

7
GRAPH THEORY (BCS405B) 2024

1) Find the graph 𝐺 − 𝑏 , 𝐺 − 5 and fusion of 𝑎 and 𝑏.

5
𝑎 𝑏

𝐺−𝑏 𝐺−5 fusion of 𝑎 and 𝑏.

Arbitrarily traceable graphs: A Euler graph is said to be an arbitrarily traceable graph from a vertex 𝑣 if one
can always trace Euler line from 𝑣 whenever walk arrives at a vertex, he can select any edge incident on it
which has not been previously traversed.

Arbitrarily traceable from 𝑎. Not arbitrarily traceable. Arbitrarily traceable from all vertices.

Review questions:
1. If 𝐺1 and 𝐺2 are subgraph of 𝐺 and 𝐺1 ∪ 𝐺2 = 𝐺, then how to find decomposition of 𝐺.
2. Is the number of edges in a graph and fusion graph are same?
3. Is graph 𝐺 − 𝑣 is null graph implies 𝐺 is null graph?
4. Suppose 𝐺 is arbitrarily traceable from 𝑎, is it necessary that 𝑎 is present in every circuit of 𝐺 ?
5. If fusion graph contains 4 vertices, then how many vertices are there in the graph?

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

8
GRAPH THEORY (BCS405B) 2024

Lecture 5: (Tutorial) 𝐊𝐨𝐧𝐢𝐠𝐬𝐛𝐞𝐫𝐠‐ 𝐛𝐫𝐢𝐝𝐠𝐞 𝐩𝐫𝐨𝐛𝐥𝐞𝐦 𝐬𝐨𝐥𝐮𝐭𝐢𝐨𝐧:

In Konigsberg two islands C and D, two land arias A and B are connected by seven bridges as shown in
the figure.
A

C D

B
Problem is whether a person can start from any land area A, B, C or D walk through all the seven
bridges exactly once and then return to the starting point. Euler represented the four land areas as
vertices and the bridges as edges of a graph.
A

C D

Now the problem is to find a closed walk containing all the edges of the graph. A graph contains a Euler
line if and only if all the vertices are of even degree. But in the above graph all the vertices are of odd
degree. Therefore, no Euler line exists. And hence no one can walk through all the seven bridges exactly
once and then return to the starting point.

Review questions:
1. At least how many additional bridges are required to get a Euler line in Konigsberg‐ bridge problem.
2. Is the graph of Konigsberg-bridge problem having unicursal line?
3. If the graph of Konigsberg-bridge problem does not have unicursal line, find the minimum number of
edges whose removal graph has unicursal line.

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

9
GRAPH THEORY (BCS405B) 2024

Lecture 6: Hamiltonian paths and circuits.

Hamiltonian circuits: A circuit in a connected graph 𝐺 is said to be Hamiltonian if it includes every vertex of 𝐺.

Hamiltonian path: A path containing all the vertices of the graph is called Hamiltonian path. If we remove any
one edge from a Hamiltonian circuit we get Hamiltonian path.

𝑏 2 𝑐
3
1 𝑑
7 6
4
𝑎 5 𝑒

Some Hamiltonian circuits are 𝑎1𝑏2𝑐3𝑑4𝑒5𝑎, 𝑎7𝑐3𝑑4𝑒6𝑏1𝑎.

Some Hamiltonian paths are 𝑎1𝑏2𝑐3𝑑4𝑒, 𝑎7𝑐3𝑑4𝑒6𝑏, 𝑎1𝑏6𝑒4𝑑3𝑐.
Graph containing Hamiltonian path but not Hamiltonian circuit.

𝑓 5 𝑒
𝑎 4
6 7 𝑑
1
3
𝑏 2 𝑐

𝑎1𝑏2𝑐6𝑓5𝑒4𝑑 is a Hamiltonian path.

𝑛−1
Theorem: If n is an odd number≥ 3, then 𝐾𝑛 contains edge disjoint Hamiltonian circuits.
2
𝑛(𝑛−1) 𝑛−1
Proof: Since 𝐾𝑛 contains edges and each Hamiltonian circuit contains 𝑛 edges, there are at most
2 2
𝑛−1
edge disjoint Hamiltonian circuits possible. For odd 𝑛, there are edge disjoint Hamiltonian circuits
2
can be shown as follows:
The sub graph of a complete graph 𝐾𝑛 given below is a Hamiltonian circuit.

5
3 𝑛−2

2 𝑛
1
𝑛−1
4
𝑛−3

360 360
Keeping the vertices fixed on a circle, rotate the polygonal pattern clockwise by 𝑛−1 , 2 × 𝑛−1 ,
360 (𝑛−3) 360
3 × 𝑛−1 ⋯ ⋯ ⋯ , × 𝑛−1 degrees.
2

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

10
 GRAPH THEORY (BCS405B) 2024

Clearly each rotation produces a Hamiltonian circuit that has no edge in common with any of the previous
ones.
(𝑛−3)
Thus, we have new Hamiltonian circuits, all edge disjoints from the one given in the figure
2
and also, edge disjoint among themselves.
(𝑛−3) 𝑛−1
Therefore, there are +1= edge disjoint Hamiltonian circuits in 𝐾𝑛 .
2 2

Example: Edge disjoint Hamiltonian Circuits of 𝐾9 .

5
5
3 7
3 7

2 9
1 2 9
1

4 8
4 8
6
6

5 5

3 7 3 7

1
2 1 9 2 9

4 8 8
4

6 6

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

11
GRAPH THEORY (BCS405B) 2024

(𝒏−𝟏)!
Theorem: If 𝑛 ≥ 3, prove that distinct Hamiltonian circuits in the complete graph 𝐾𝑛 is .
𝟐

Proof: Let 𝑋 be the number of distinct Hamiltonian circuits in 𝐾𝑛 . Consider one such circuit.

Let it be 𝑣1 − 𝑣2 − 𝑣3 − ⋯ ⋯ − 𝑣𝑛−1 − 𝑣𝑛 − 𝑣1 .

If we remove any edge from this, we get Hamiltonian path.

𝑣1 − 𝑣2 − 𝑣3 − ⋯ ⋯ − 𝑣𝑛−1 − 𝑣𝑛 (Row permutations are 𝑣1 𝑣2 𝑣3 ⋯ 𝑣𝑛−1 𝑣𝑛 , 𝑣𝑛 𝑣𝑛−1 ⋯ 𝑣3 𝑣2 𝑣1 . )

𝑣2 − 𝑣3 − 𝑣4 − ⋯ ⋯ − 𝑣𝑛 − 𝑣1
𝑣3 − 𝑣4 − 𝑣5 − ⋯ ⋯ − 𝑣1 − 𝑣2
⋮
𝑣𝑛 − 𝑣1 − 𝑣2 − ⋯ ⋯ − 𝑣𝑛−2 − 𝑣𝑛−1
Therefore, there are n distinct Hamiltonian paths in each Hamiltonian circuit, and 2 row permutations from each
Hamiltonian path. Number of row permutations of n symbols are 𝑛!.
(𝑛−1)!
Therefore 2𝑛𝑋 = 𝑛! ⟹ 𝑋 = .
2

Review questions:

1. Whether all the Eulerian graph contains Hamiltonian circuit?

2. If the graph is Hamiltonian, then is it contains Hamiltonian path?
3. If the graph is Hamiltonian, then is it Euler graph?
4. Whether a Hamiltonian graph contains Unicursal line?
5. For what value of 𝑛 a complete graph 𝐾𝑛 has only Unicursal line and Hamiltonian path?
6. Find the number of distinct Hamiltonian circuit in 𝐾6 .

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

12
GRAPH THEORY (BCS405B) 2024

Lecture 7: Directed graph (Digraph).

Directed graph (Digraph): Let 𝑉 be a nonempty set, and 𝐸 ⊆ 𝑉 × 𝑉. The pair 𝐺( 𝑉, 𝐸 ) is called directed
graph or digraph.

In-degree and out-degree: The number of edges in 𝐺 that are incident into the vertex 𝑣 is called in-degree of 𝑣
and denoted by 𝑜𝑑(𝑣) or 𝑑+ (𝑣).

The number of edges in 𝐺 that are incident from the vertex 𝑣 (incident out of the vertex 𝑣) is called out-degree
of 𝑣 and denoted by 𝑖𝑑(𝑣) or 𝑑 − (𝑣).

In a digraph isolated vertex is a vertex in which the in-degree and out- degree are both equal to zero.

For a vertex 𝑣 of a digraph 𝐺 if 𝑑 + (𝑣) + 𝑑 − (𝑣) = 1 then 𝑣 is a pendent vertex.

Two directed edges are said to be parallel if they are incident from the same vertex and incident into the same
vertex.

Types of digraphs:

1. Simple digraphs: A digraph that has no self-loop and parallel edges is called simple digraph.

Example:

2. Asymmetric or antisymmetric digraphs: Digraphs that have at most one directed edge between a pair of
vertices, but are allowed to have self-loops are called asymmetric digraphs. That means at the most one of the
edge(𝑎, 𝑏), (𝑏, 𝑎) ∈ 𝐸 for any 𝑎, 𝑏 ∈ 𝑉.

Complete asymmetric digraphs: Digraphs that have exactly one directed edge between every pair of vertices.
That means exactly one of the edge(𝑎, 𝑏), (𝑏, 𝑎) ∈ 𝐸 for any 𝑎, 𝑏 ∈ 𝑉.

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

13
GRAPH THEORY (BCS405B) 2024

3. Symmetric digraphs: Digraphs in which if (𝑎, 𝑏) ∈ 𝐸 then (𝑏, 𝑎) ∈ 𝐸 for any 𝑎, 𝑏 ∈ 𝑉.

Complete symmetric digraphs: A digraph in which there is exactly one edge directed from every vertex to every
other vertex.

4. Balanced digraphs or isographs: A digraph is said to be balanced if 𝑑+ (𝑣) = 𝑑 − (𝑣) for every vertex 𝑣 of 𝐺.

5. Regular digraphs: In a balanced digraphs all the vertices are of same in-degree and same out- degree then it is
regular.

Review questions:

1. An asymmetric digraph can have parallel edges?

2. Undirected graph associated with a complete asymmetric digraph without self-loop is?

3. Number of directed edges in a complete symmetric digraph without self-loop with 𝑛 vertices is?

4. Number of edges in k-regular digraph is?

5. Whether a symmetric digraph can have parallel edges?

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

14
GRAPH THEORY (BCS405B) 2024

Lecture 8: Digraphs and binary relations.

Digraphs and binary relations: A subset of 𝐴 × 𝐴 is called a binary relation on 𝐴.
Every non-empty relation on a finite set can be represented by a digraph without parallel edges, and every
digraph without parallel edges defines a binary relation on the set of vertices.
Reflexive relation:
A relation ℛ on a set 𝐴 is called reflexive if ∀ 𝑥 ∈ 𝐴, (𝑥, 𝑥) ∈ ℛ (or 𝑥ℛ𝑥 ).

Symmetric relation: A relation ℛ on a set 𝐴 is called symmetric

if (𝑥, 𝑦) ∈ ℛ ⟹ (𝑦, 𝑥) ∈ ℛ , ∀ 𝑥, 𝑦 ∈ 𝐴 (or 𝑥ℛ𝑦 ⟹ 𝑦ℛ𝑥, ∀ 𝑥, 𝑦 ∈ 𝐴 ).

Transitive relation: A relation ℛ on a set 𝐴 is called transitive,

if (𝑥, 𝑦), (𝑦, 𝑧) ∈ ℛ ⟹ (𝑥, 𝑧) ∈ ℛ , ∀ 𝑥, 𝑦, 𝑧 ∈ 𝐴 .
(or 𝑥ℛ𝑦 𝑎𝑛𝑑 𝑦ℛ𝑧 ⟹ 𝑥ℛ𝑧, ∀ 𝑥, 𝑦, 𝑧 ∈ 𝐴 ).

Anti-symmetric relation: A relation ℛ on a set 𝐴 is called antisymmetric,

If ∀ 𝑥, 𝑦 ∈ 𝐴 , (𝑥, 𝑦), (𝑦, 𝑥) ∈ ℛ ⟹ 𝑥 = 𝑦.
Or, if 𝑥 ≠ 𝑦 then at the most one of the (𝑥, 𝑦) & (𝑦, 𝑥) belongs to ℛ.

Irreflexive relation: A relation ℛ on a set 𝐴 is called irreflexive if ∀ 𝑥 ∈ 𝐴, (𝑥, 𝑥) ∉ ℛ .

Note: Every reflexive relation is not irreflexive, and every irreflexive relation is not reflexive,
but there are relations which are neither reflexive nor irreflexive.

1. Consider the following relations on 𝐴 = {1, 2, 3}

1. ℛ = {(1, 1), (2, 2)(3, 3), (1, 2)} is reflexive but not irreflexive.
2. ℛ = {(1, 3), (2, 3)(3,1), (1, 2)} is irreflexive but not reflexive.
3. ℛ = {(1, 1), (3, 1), (1, 2)} is neither reflexive nor irreflexive.

2. Let 𝑅 be a relation on 𝐴 = {1, 2, 3, 4} such that,

𝑅 = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (2, 3), (1, 3), (3, 4)(4, 3) }
Check whether the relation is reflexive, irreflexive, symmetric, antisymmetric, or transitive. Justify your
answer. Draw the digraph.
Since (1, 1), (2, 2)(3, 3), (4, 4) ∈ 𝑅, 𝑅 is reflexive but not irreflexive.
(1, 3) ∈ 𝑅 but (3, 1) ∉ 𝑅 ⟹ 𝑅 is not symmetric.
(1, 2), (2, 1) ∈ 𝑅 𝑏𝑢𝑡 1 ≠ 2 ⟹ 𝑅 is not antisymmetric.
(1, 3), (3, 4) ∈ 𝑅 𝑏𝑢𝑡 (1, 4) ∉ 𝑅 ⟹ 𝑅 is not transitive.

1 2

4
3

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

15
GRAPH THEORY (BCS405B) 2024

Let 𝐴 = {1, 2, 3} some examples of relations on A is given below.

Reflexive Symmetric Transitive Relation ℛ on 𝐴

   {(1, 2), (2, 3)}

   {(1, 2), (1, 3)}

   {(1, 2), (2, 1)}

   {(1, 1), (2, 2)}

   {(1, 1), (2, 2)(3, 3), (1, 2), (2, 3)}

   {(1, 1), (2, 2)(3, 3), (1, 2)}

   {(1, 1), (2, 2)(3, 3), (1, 2), (2, 1), (1, 3), (3,1)}

   {(1, 1), (2, 2)(3, 3)} , 𝐴 × 𝐴 .

Symmetric Anti-Symmetric Relation ℛ on 𝐴

  {(1, 2), (2, 1), (2, 3)}

  {(1, 2), (2, 3)}

  {(1, 2), (2, 1)}

  {(1, 1), (2, 2)}

Review questions:
1. How to verify reflexive relation from digraph?
2. How to verify symmetric relation from digraph?
3. If the relation is irreflexive then its digraph is?
4. Explain the digraph of anti-symmetric relation?
5. If a relation is both symmetric and anti-symmetric then there is no edge between any two distinct
vertices, why?

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

16
GRAPH THEORY (BCS405B) 2024

Lecture 9: Equivalence relation, Partial order relation.

Equivalence relation: A relation ℛ on a set 𝐴 is called Equivalence relation if ℛ is reflexive, symmetric and
transitive.

Examples: 1. Let 𝐴 = {1, 2, 3} , both ℛ = {(1, 1), (2, 2)(3, 3)} , and ℛ = 𝐴 × 𝐴 are equivalence relations
on 𝐴.

2. For a fixed integer 𝑛 > 1, Prove that the relation “Congruent modulo 𝑛” is an equivalence relation on the
set of all integers ℤ.

Equivalence class: Let ℛ be an equivalence relation on 𝐴 , For each element 𝑥 ∈ 𝐴 equivalence class of 𝑥, is
defined by [𝑥] = {𝑦 ∈ 𝐴|(𝑦, 𝑥) ∈ ℛ}.

A graph representing an equivalence relation is called equivalence graph. Because of the symmetry in
equivalence graph if (𝑎, 𝑏) ∈ 𝐸 then (𝑏, 𝑎) ∈ 𝐸, hence two directed edges can be replaced by a single
undirected edge. Since equivalence relation is reflexive, each vertex of equivalence graph contains self-loop and
hence we can ignore self-loops in equivalence graph.

Example: ℛ = {(1, 1), (2, 2)(3, 3), (4, 4), (1, 2), (2, 1), (1, 3), (3,1), (2, 3), (3, 2)} is an equivalence relation on
the set = {1, 2, 3, 4} .

Simplified equivalence graph of ℛ is given below.

1 2

4 3

Partition of a set 𝑨: Given a set 𝐴 and an index set 𝐼, Let ∅ ≠ 𝐴𝑖 ⊆ 𝐴 for each 𝑖 ∈ 𝐼. Then {𝐴𝑖 }𝑖∈𝐼 is a
partition of 𝐴 if i) 𝐴 = ⋃𝑖∈𝐼 𝐴𝑖 ii) 𝐴𝑖 ∩ 𝐴𝑗 = ∅, for all 𝑖, 𝑗 ∈ 𝐼 with 𝑖 ≠ 𝑗 .
Each subset 𝐴𝑖 is called a cell or block of the equation.
Or the nonempty subsets 𝐴1 , 𝐴2 , 𝐴3 ⋯ ⋯ 𝐴𝑛 form a partition of 𝐴 if
i) 𝐴 = 𝐴1 ∪ 𝐴2 ∪ 𝐴3 ⋯ ⋯ ∪ 𝐴𝑛 .
ii) 𝐴𝑖 ∩ 𝐴𝑗 = ∅, for 𝑖 ≠ 𝑗 .

Every equivalence relation partitions the vertex set and every partitions determines an equivalence relation.
Simplified equivalence graph contains components, each components of equivalence graph is a complete graph.

1. ℛ = {(1, 1), (2, 2)(3, 3), (4, 4), (5, 5), (1, 2), (2, 1), (1, 3), (3,1), (2, 3), (3, 2), (4, 5), (5, 4)} is an equivalence
relation on 𝐴 = {1, 2, 3, 4, 5}. Find the partition induced by ℛ on 𝐴 and draw simplified digraph.
Solution: Distinct equivalence classes are [1] = {1, 2, 3} = [2] = [3] and [4] = {4, 5} = [5].

Therefore, partition induced by ℛ on 𝐴 is 𝐴 = {1, 2, 3} ∪ {4, 5}.

1 2

Simplified equivalence graph. 5

3 4

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

17
GRAPH THEORY (BCS405B) 2024

Undirected edge represents two directed edges in opposite directions. Assume self-loop at every vertex.
Clearly each component of simplified equivalence graph is a complete graph.

Partial order relation: A relation ℛ on a set 𝐴 is called Partial order if ℛ is reflexive, anti-symmetric and
transitive. The order pair (𝐴, ℛ) is called poset.

Examples:
1. Set 𝐴 = {1, 2, 3, 4, 6, 9} with divisibility relation ℛ is poset.
Solution: Divisibility relation ℛ is defined by 𝑎ℛ𝑏 or (𝑎, 𝑏) ∈ ℛ ⟺ 𝑎|𝑏 or 𝑏 = 𝑘𝑎 for some integer 𝑘
i. Clearly 𝑎|𝑎 for all 𝑎 ∈ 𝐴, since 𝑎 is nonzero. ⟹ ∀ 𝑎 ∈ 𝐴, (𝑎, 𝑎) ∈ ℛ .
Therefore, ℛ is reflexive.
ii. If 𝑎|𝑏 and 𝑏|𝑎 then 𝑎 = 𝑏 for all 𝑎, 𝑏 ∈ 𝐴, since A contains only positive numbers.
That is, ∀ 𝑎, 𝑏 ∈ 𝐴 , (𝑎, 𝑏), (𝑏, 𝑎) ∈ ℛ ⟹ 𝑎 = 𝑏.
Therefore, ℛ is Anti-symmetric.
iii. If 𝑎|𝑏 and 𝑏|𝑐 then 𝑏 = 𝑘1 𝑎 and 𝑐 = 𝑘2 𝑏 ⟹ 𝑐 = 𝑘2 𝑘1 𝑎 ⟹ 𝑎|𝑐.
That is, ∀ 𝑎, 𝑏, 𝑐 ∈ 𝐴 , (𝑎, 𝑏), (𝑏, 𝑐) ∈ ℛ ⟹ (𝑎, 𝑐) ∈ ℛ.
Therefore ℛ is transitive.
Hence ℛ is partial order relation on 𝐴 and (𝐴, ℛ) is poset.

Review questions:

1. Is there a relation which is both reflexive and irreflexive?

2. Is there a relation which is both symmetric and anti-symmetric?

3. Is the complete symmetric digraph is equivalence graph?

4. Is there a relation which is both equivalence and partial order relation?

5. Find all equivalence relation on set 𝐴 = {1, 2, 3}.

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

18
GRAPH THEORY (BCS405B) 2024

Lecture 10: (Tutorial) Traveling salesmen problem.

TRAVELING-SALESMAN PROBLEM: A problem closely related to the question of Hamiltonian circuits 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 𝑒𝑖 there is associated a real number (the distance in miles, say), 𝑊(𝑒𝑖 ).

Such a graph is called a weighted graph; 𝑊(𝑒𝑖 ) being the weight of edge 𝑒𝑖 . In our problem, if each of the
cities has a road to every other city, we have a complete weighted graph.

This graph has numerous Hamiltonian circuits, 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 circuits in a complete
graph of 𝑛 vertices is (𝑛 − 𝑙)!/2. This follows from the fact that starting from any vertex we have 𝑛 − 1
edges to choose from the first vertex, 𝑛 − 2 from the second, 𝑛 − 3 from the third, and so on. These being
independent choices, we get (𝑛 − 1)! possible number of choices. This number is, however, divided by 2,
because each Hamiltonian circuit has been counted twice.

Theoretically, the problem of the traveling salesman can always be solved by enumerating all (𝑛 − 𝑙)!/2
Hamiltonian circuits, calculating the distance traveled in each, and then picking the shortest one. However, for a
large value of 𝑛, the labor involved is too great even for a digital computer (try solving it for the 50 state
capitals in the United States; 𝑛 = 50).

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.
Since this problem has applications in operations research, some specific large-scale examples have been
worked out.
There are also available several heuristic methods of solution that give a route very close to the shortest one, but
do not guarantee the shortest.

DEPARTMENT OF CUMPUTER SCIENCE & ENGINEERING /C.E.C.

19