MODULE 5

Introduction to Graph Theory: Definitions and Examples, Sub graphs,

Complements and Graph Isomorphism, Vertex Degree, Euler Trails and
Circuits.

Subject
Operation on Graphs:
Consider two graphs G1=(V1,E1) and G2=(V2,E2).
 The graph where the vertex set is 𝑉1 ∪ 𝑉2 and the edge set 𝐸1 ∪ 𝐸2 is called
the union of G1 and G2, it is denoted by 𝐺1 ∪ 𝐺2 . Thus,
𝐺1 ∪ 𝐺2 = 𝑉1 ∪ 𝑉2 , 𝐸1 ∪ 𝐸2 .

 The graph where the vertex set is 𝑉1 ∩ 𝑉2 and 𝑉1 ∩ 𝑉2 ≠ ∅ , the edge set is
𝐸1 ∩ 𝐸2 , is called the intersection of G1 and G2 . Thus,
𝐺1 ∩ 𝐺2 = 𝑉1 ∩ 𝑉2 , 𝐸1 ∩ 𝐸2 .

 The graph where the vertex set is 𝑉1 ∪ 𝑉2 and the edge set is 𝐸1 ∆ 𝐸2 , where
𝐸1 ∆ 𝐸2 is the symmetric difference of E1 and E2 . This graph is called the ring
sum of G1 and G2. It is denoted by 𝐺1 ∆ 𝐺2 .
𝐺1 ∆𝐺2 = 𝑉1 ∪ 𝑉2 , 𝐸1 ∆𝐸2 .

 Decompostion: The graph G is decomposed (or partitioned) into two subgraphs

G1 and G2 if 𝐺1 ∪ 𝐺2 = 𝐺 𝑎𝑛𝑑 𝐺1 ∩ 𝐺2 = 𝑁𝑢𝑙𝑙 𝑔𝑟𝑎𝑝ℎ.

 Deletion: If v is a vertex in a graph G, then G – v denotes the subgraph of G

obtained by deleting v and all edges incident on v, from G. This
Subgraph G-v, is referred as vertex-deleted subgraph of G.

Subject
  If e is an edge in a graph G, then G-e denotes the subgraph of G obtained
by deleting e (but not its end vertices) from G. This subgraph, G-e, is referred
to as edge-deleted subgraph of G.
Since deletion of an edge does not alter the number of vertices, an edge deleted
subgraph of a graph is a spanning subgraph of the graph.

 Complement of a Subgraph: Given a graph G and a subgraph G1 of G, the

subgraph of G obtained by deleting from G all the edges that belong to G1 is called
the complement of G1 in G; it is denoted by G - G1 or 𝐺1 .
i.e., 𝐺1 = 𝐺 − 𝐸1 Also 𝐺1 = 𝐺∆𝐺1 .

 Complement of a Simple graph: Every simple graph of order n is a subgraph of

the complete graph Kn . If G is a simple graph of order n, then the complement of G
in Kn is called the complement of G; it is denoted by 𝐺 .
i.e., 𝐺 = 𝐾𝑛 − 𝐺 = 𝐾𝑛 ∆𝐺.

Subject
 Exercises:
(1) Find the union, intersection and the ring sum of the graphs G1 and G2 given

G1 G2

Solution:

𝐺1 ∪ 𝐺2 𝐺1 ∩ 𝐺2 𝐺1 ∆𝐺2

Subject
(2) For the graph G shown below, find G-v and G-e.

v
e
Solution:

G-v G-e
(3) For the graph G and its subgraphs G1 and G2 shown below, find 𝐺1 𝑎𝑛𝑑 𝐺2

G G1 G2
Solution:

Subject
𝐺1 𝐺2
 (4) For the given graph K6 , sub graph is shown below, write the complement.

K6 G
Solution:

This graph is known as David graph.

Subject
 (5) Find the complement of each of the following simple graphs

Solution:

(6) If G is a simple graph of order n and the size of G is 56 and the size of 𝐺
is 80. what is n?
Solution:
We know that 𝐺 = 𝐾𝑛 − 𝐺.
∴ size of 𝐺 = 𝑠𝑖𝑧𝑒 𝑜𝑓 𝐾𝑛 − (𝑠𝑖𝑧𝑒 𝑜𝑓 𝐺)
1
80 = 2 𝑛 𝑛 − 1 − 56
𝑛 𝑛 − 1 = 160 + 112 = 272 = 17𝑥16.
∴ 𝑛 = 17

Subject
Walks and their classification:
We have five important subgraphs of a graph, they are a walk, a trail, a circuit, a path and
a cycle.

Walk: Let G be a graph having at least one edge. A finite alternating sequence of vertices and
edges of the form 𝑣𝑖 𝑒𝑗 𝑣𝑖+1 𝑒𝑗+1 𝑣𝑖+2 … … . , 𝑒𝑘 𝑣𝑚 which begins and ends with vertices and
which is such that each edge in the sequence is incident on 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 can appear more than once.
• No. of edges present in a walk is called its length.
• The vertex with which a walk begins is called the initial vertex (origin) of the walk.
• The vertex with which a walk ends is called the final vertex (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.
• Non terminal vertices of a walk are called its internal vertices.
• A walk having u as the initial vertex and v as the final vertex is called a walk from u
to v or u-v walk.
• A walk that begins and ends at the same vertex is called a closed walk.
• A walk which is not closed is called an open walk.
Trail and Circuit:
An Open walk in which no edge appears more than once, then the
walk is called a trail. A Closed walk in which no edge
Subject
appears more than once is called a circuit.
 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.
Examples:
(1) For the graph

v e2 v3 e
8
e1 v6
2
v1 e3 e5
e7
e4
e6
v5 v4

v1e1v2e2v3e8v6 ----- is a walk of length 3

v1e4v5e3v2e2v3e5v5e6v4 ----- is a walk of length 5
v1e1v2e3v5e4v1 ----- is a closed walk
v1e1v2e2v3e5v5 ----- is an open walk
v1e1v2e3v5e3v2e2v3 ----- is an open walk but not a trail (e3 is repeated)
v1e4v5e3v2e2v3e5v5e6v4 ----- is an open walk and a trail
v1e1v2e3v5e3v2e2v3e5v5e4v1 ----- is a closed walk but not a
circuit (e3 is repeated)
v1e1v2e3v5e5v3e7v4e6v5e4v1 ------ is a closed walk and a circuit.
Subject
 (2) For the graph shown in the figure, indicate the nature of the following walks.
(i) v1e1v2e2v3e2v2 (ii) v4e7v1e1v2e2v3e3v4e4v5 (iii) v1e1v2e2v3e3v4e4v5
(iv) v1e1v2e2v3e3v4e7v1 (v) v6e5v5e4v4e3v3e2v2e1v1e7v4e6v6
e1
v6 v1 v2
e6
e5 e7 e2

v5 e4 v4 e3 v3
Solution:
(i) Open walk but not a trail
(ii) Trail which is not a path
(iii) Trail which is a path
(iv) Closed walk which is a cycle
(v) Closed walk which is a circuit but not a cycle

(3) For the graph shown, find the nature of the following walks:
(i) ABEFDACDB (ii) ABEFDCA (iii) ACDFEBDA (iv)ABDFEBDC
B E
D
A F G

C H
Subject
(4) Prove the following:
(i) A path with n vertices is of length n-1.
(ii) If a cycle has n vertices, it has n edges.
(iii) The degree of every vertex in a cycle is two.
Proof: (i) In a path, every vertex, except the last vertex, is followed by one edge.
Hence if a path has n vertices, it must have n-1 edges and length is n-1.
(ii) In a cycle, every vertex is followed by one edge. Hence, if a cycle has n
Vertices, it must have n edges.
(iii) In a cycle, exactly two edges are incident on every vertex. Hence the
degree of every vertex in a cycle is two.

(5) Prove that, in a graph, there is a u-v trail if and only if there is a u-v path.
Proof: Since every path is a trail, if there is a u-v path, it is automatic that there is
a u-v trail. Therefore, we need only to prove that if there is u-v trail then there is a u-v path.
Assume that there is a u-v trail in the graph being considered. Among these trails,
Choose a trail of minimum length, and denote it by
v0v1v2……vn --------- (i)
where v0= u and vn= v; and the edges between the vertices are understood.
Case(1) If there is only one u-v trail, it will be the one with minimum length.
Case(2) If in the trail, no vertex is repeated then it is a path from
u to v, and the proof is over, otherewise the trail (i) will be of the form

Subject
 v0v1v2…….vi-1vivi+1….vj-1vjvj+1….vn -----------(ii)
where vj=vi for some vi and vj.
Consider the trail
v0v1v2…….vi-1vivj+1…..vn……..(iii)
which is got by skipping the vertices vi+1 , vi+2,….vj-1,vj together with all
edges preceding them. Evidently, this trail is shorter than the trail (ii) and we
have a contradiction. Hence, the trail with minimum length has to be a path.
Hence the proof.

Subject
Connected and Disconnected Graphs:
A graph G is said to be connected graph if every pair of distinct vertices in G are
connected. That is, in 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.
Otherwise, G is called a disconnected graph.
A digraph D is said to be connected or disconnected according as its underlying graph G
is connected or disconnected.

Note: In a graph G, all walks, all trails, all circuits, all paths and all cycles (if they exist)
are connected subgraphs of G.

Every non trivial graph G consists of one or more connected graphs. Each such connected
Graph is a subgraph of G and is called a component of G.

If u and v are two vertices in a connected graph, then the length of the shortest path that is
the path containing least number of edges is called the distance between u and v.

Theorem: If a graph has exactly two vertices of odd degree, then there must be a
path connecting these vertices.
Proof: Denote the two vertices of odd degree by v1 and v2.
Suppose there is no path Connecting these. Then the graph
is disconnected and v1 and v2 belong to two different
Subject
Components, say H1 and H2. Consequently, each of H1 and H2 contains only one
vertex of odd degree. This is not possible, because H1 and H2 are graphs and in
a graph the number of vertices of odd degree is always even. Hence, there must
be a path connecting v1 and v2. Hence the proof.

Theorem : A simple graph with n vertices and k components can have at most
1
𝑛 − 𝑘 𝑛 − 𝑘 + 1 number of edges.
2
Proof:
In the given graph G, let n1 be the number of vertices in the first component, n2
Be the number of vertices in the second component ……. and nk be the number of
vertices in the kth component. Then
𝑛1 + 𝑛2 + ⋯ … . +𝑛𝑘 = 𝑛 (i)
This gives
𝑛1 − 1 + 𝑛2 − 1 + ⋯ … . + 𝑛𝑘 − 1 = 𝑛 − 1 + 1 + 1 + ⋯ … (k terms)
= 𝑛 − 𝑘.

Squaring both sides, we get

(𝑛1 − 1)2 +(𝑛2 − 1)2 + ⋯ … … + 𝑛𝑘 − 1 2 + 𝑆 = 𝑛 − 𝑘 2 (ii)
Where S is the sum of products of the form 2(ni-1)(nj-1),
i = 1,2,……k, 𝑖 ≠ 𝑗
Since each of n1, n2, ……..nk is greater than or equal to 1, we
have 𝑆 ≥ 0.
Subject
Therefore, (ii) yields
(𝑛1 − 1)2 +(𝑛2 − 1)2 + ⋯ … . . +(𝑛𝑘 − 1)2 ≤ (𝑛 − 𝑘)2
or 𝑛1 2 + 𝑛2 2 + ⋯ … . +𝑛𝑘 2 − 2 𝑛1 + 𝑛2 + ⋯ … + 𝑛𝑘 + 𝑘 ≤ (𝑛 − 𝑘)2
or 𝑛1 2 + 𝑛2 2 + ⋯ … … + 𝑛𝑘 2 ≤ 𝑛 − 𝑘 2 + 2𝑛 − 𝑘, using (i)
= 𝑛2 + 𝑘 2 − 2𝑛𝑘 + 2𝑛 − 𝑘
= 𝑛2 − (𝑘 − 1)(2𝑛 − 𝑘)

𝑘 2
i.e., 𝑖=1 𝑛𝑖 ≤ 𝑛2 − (𝑘 − 1)(2𝑛 − 𝑘) (iii)

Now, since G is a simple graph, each of the components of G is a simple graph.

Therefore, the maximum number of edges which the ith component can have is
1
𝑛 𝑛 −1 .
2 𝑖 𝑖
Therefore, the maximum number of edges which G can have is N, where

1𝑘
𝑁=2 𝑖=1 𝑛𝑖 (𝑛𝑖 − 1) (iv)
1
= 2 𝑘𝑖=1 𝑛𝑖 2 − 𝑛𝑖
1 1
= 2 𝑘𝑖=1 𝑛𝑖 2 − 2 𝑘𝑖=1 𝑛𝑖
1 1
≤ 2 𝑛2 − 𝑘 − 1 2𝑛 − 𝑘 − 2𝑛
1
= 2 𝑛2 − 2𝑛𝑘 + 𝑛 + 𝑘 2 − 𝑘
1
=2 𝑛−𝑘 𝑛−𝑘+1
Subject
Theorem: A connected graph with n vertices has at least n-1 edges.
Proof : Since the graph is connected, 𝑛 ≥ 2. If m denotes the number of edges, we have to
Prove that 𝑚 ≥ 𝑛 − 1, for every positive integer 𝑛 ≥ 2.
Applying Induction method,
When n = 2. Then there are exactly two vertices in the graph and since the graph is
Connected, there must be at least one edge joining there vertices. Thus, now,
𝑚 ≥1= 2−1 = 𝑛−1 . Verifies for n = 2.

Assume that the result 𝑚 ≥ 𝑛 − 1 holds for all connected graphs with n = k number of
Vertices, where k is a positive integer ≥ 2.

Now, consider a connected graph, say Gk+1, with k+1 vertices. Choose a vertex v of this graph
and consider the graph Gk obtained by deleting an edge from Gk+1 for which v is an end
vertex.
Then, Gk is a connected graph with k vertices. Let mk be the number of edges in Gk.
Then from the assumption made in the preceding paragraph we have 𝑚𝑘 ≥ 𝑘 − 1.
Consequently, 𝑚𝑘 + 1 ≥ 𝑘 + 1 − 1.
But, 𝑚𝑘 + 1 is the number of edges in Gk+1 and k+1 is the number of vertices in Gk+1. Thus,
the result 𝑚 ≥ 𝑛 − 1 holds for n = k+1 when it holds for 𝑛 = 𝑘 ≥ 2.
Hence, by induction, the result holds for all integers 𝑛 ≥ 2.
Hence the proof.

Subject
Theorem : A graph G is disconnected if and only if its vertex set V can be partitioned
into two non-empty disjoint subsets V1 and V2 such that there exists no edge in G
whose one end vertex is in V1 and the other is in V2.
Proof: Suppose G is a disconnected graph. Consider a vertex v in G. Let V1 be the
set of all vertices in G that are connected to v. Since G is disconnected, V1 does not
Include all vertices of G. This means that V1 is a proper subset of V. Let V2=V-V1 .
Then 𝑉1 ∩ 𝑉2 = ∅, 𝑉 = 𝑉1 ∪ 𝑉2 and no vertex in V1 is connected to any vertex in V2.
Hence, V1 and V2 form a partition of V of the desired type.

Conversely, suppose two subsets V1 and V2 of V form a partition of V of the desired

type.
Consider two arbitrary vertices v and u in G, such that 𝑣 ∈ 𝑉1 and 𝑢 ∈ 𝑉2 . Then there
exists no path between v and u. Hence G is not connected.
Hence the proof.

(1) Prove that a connected graph G remains connected after removing an edge e
from G if and only if e is a part of some cycle in G.
Proof: Suppose e is a part of some cycle C in G. Then the end vertices of e (say A
and B) are joined by at least two paths, one of which is e and the other C-e.
Hence the removal of e from G will not affect the connectivity of G;
because even

Subject
after the removal of e the end vertices of e (i.e., A and B) remain connected through
the path C-e.
A

Conversely, suppose e is not a part of any cycle in G. Then the end vertices of e
Are connected by at most one path. Hence the removal of e from G disconnects
these end points. This means that G-e is a disconnected graph. Thus, if e is not a
part of any cycle in G then G – e is disconnected. This is equivalent to saying that
if G – e is connected ( that is if G remains connected after the removal of e from G),
Then e belongs to some cycle in G (contrapositive). Hence the proof.

Subject
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.
 Since Euler circuits and Euler trails include all edges, they automatically should include
all vertices as well.
 A connected graph that contains an 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 a semi-
Eulerian graph or unicursal graph).

Subject
 Examples:
(1) Show that the graph shown is a Euler graph
A B

P Q R

Solution: The closed walk PAQBRQP is a circuit that contains all edges of G.
This is a Euler circuit. Therefore the given graph is Euler graph.

(2) Find an Euler circuit in the graph shown

v2
v1 v3

v9 v11 v4
v10

v8 v5
v7 v6
Solution:
The Euler circuit is v1v2v9v10v2v11v7v10v11v6v4v2v3v4v5v6v7v8v9v1.

Subject