MODULE 3

INTRODUCTION TO GRAPH THEORY

Introduction:
 A graph is used to represent data consisting of discrete objects and to
show the relationship between these objects in a simple graphical
manner
 a graph is interpreted as a series of dots which are either linked or not
linked to one another by lines.
 Each dots is known as a vertex and the line joining two vertices is known
as an edge
 Vertex is singular
 Vertices is plural

Here’s how the graph G=(V,E) with

V={A,B,C,D} E={{A,B},{A,C},{B,C},{C,D}}

There’s an edge between A and B

An edge between A and C

 An edge between B and C

An edge between C and D

Directed Graph

 A directed graph (or digraph) is a set of vertices connected by directed

edges, which have a specific, one-way direction, unlike undirected
graphs where edges are bidirectional.

 If there's an edge from vertex A to vertex B, it doesn't automatically

mean there's an edge from B to A.

Basic Graph Terminologies

Adjacency: In a graph G two vertices u and v are said to be adjacent if they

are the endpoints of an edge.

Example:

In the above Graph A is adjacent to :B,C

B is adjacent to A and C

C is adjacent to A,B and D

D is adjacent to C

Multiple Edges: Two vertices are connected by more than one edge. The sum
of degree is twice the number of edges
 Graph 1 Graph 2

Degree of a Vertex
 It is the number of vertices adjacent to a vertex V.
 It is denoted as deg(V).
 In a simple graph with n number of vertices, the degree of any vertices is
: deg(v) = n – 1 ∀ v ∈ G
 The minimum degree (δ(G)) of a graph is the lowest number of edges
connected to any single vertex.
 The maximum degree (Δ(G)) is the greatest number of edges
connected to any single vertex.
 To find them, you count the edges incident to each vertex; the smallest
count is the minimum degree, and the largest count is the maximum
degree.
Min Degree 𝜹(𝑮) = 𝟎
Max Degree Δ(G) = 3

Isolated Vertex:
 A vertex with degree 0 is called an isolated vertex
 In the above Graph, V5 is an isolated Vertex
Pendant Vertex:
 Vertex with degree 1 is called a leaf or pendant vertex.
 In the above Graph, V3 is a Pendant Vertex
Loop:
In graph theory, a loop (or self-loop) is an edge that connects a vertex to
itself, forming a closed path.
Loops are a type of edge that contributes two to the degree of a vertex.

Question 1: Find the degree of each vertex

  In case of directed graphs, the degree is further classified as in-degree
and out-degree.
 The in-degree of a vertex is the total number of edges that are directed
into that vertex
 The out-degree of a vertex indicating the total count of outgoing
connections from that node
 In-degree is denoted as deg-(u) and out-degree is denoted as deg+(u).

In degree of a Vertex

 Indegree(V1) = 1
 indegree (V2) =2
 indegree (V3) =1
 indegree (V4) =2
 indegree (V5) =1

Out Degree
 Outdegree (V1) = 1
 Outdegree (V2) = 2
 Outdegree (V3) = 1
 Outdegree (V4) = 1
 Outdegree (V5) = 2

Types of Graphs

Simple Graph
A simple graph is an undirected graph with no loops (edges that connect a
vertex to itself) and no multiple edges between the same pair of vertices
Multi Graph

Any graph which contains some parallel edges but doesn’t contain any self-
loop is called a multigraph.

Pseudo Graph

A graph G with a self-loop and some multiple edges is called a pseudo graph

Finite Graphs

A graph is said to be finite if it has a finite number of vertices and a finite

number of edges.
Infinite Graph:

A graph is called an infinite graph if it has an infinite number of vertices and

an infinite number of edges.

Null Graph
 A null graph is a graph with no edges.
 In other words, it is a graph with only vertex and no connections
between them.
 A null graph can also be referred to as an edgeless graph, an isolated
graph, or a discrete graph

Trivial Graph

A trivial graph is a graph with only one vertex and no edges. It is also known
as a singleton graph or a single vertex graph.

Complete Graph

 A simple graph with n vertices is called a complete graph if the degree

of each vertex is n-1, that is, one vertex is attached with n-1 edges or the
rest of the vertices in the graph.
  A complete graph is also called Full Graph.
 It's denoted as Kₙ, with 'n' representing the number of vertices.
 In a complete graph, each vertex has a degree of n-1, and the total
number of edges is calculated by the formula n(n-1)/2
K₃ (a triangle):

A complete graph with 3 vertices (K₃) has 3(3-1)/2 = 3 edges, with each
vertex connected to the other two.
 K₄ (a square with diagonals):
A complete graph with 4 vertices (K₄) has 4(4-1)/2 = 6 edges, where
each vertex is connected to the other three

Weighted Graphs

 A weighted graph is a graph where each edge has a number (weight)

that represents distance, cost, or time.
 These graphs help find the shortest or cheapest paths. Examples include
Google Maps, airline routes, and delivery networks.
Regular Graph

 A regular graph is a type of undirected graph where every vertex has the
same number of edges or neighbours
 All complete graphs are regular but vice versa is not possible..
 In other words, if a graph is regular, then every vertex has the same
degree
OR
A graph with all vertices of degree 'k' is called a k-regular graph.

Degree of each vertices of this graph is 2.

So, the graph is 2 Regular.

Subgraph: A graph H is a subgraph of graph G if its vertex set V' is a subset of G's vertex
set V, and its edge set E' is a subset of G's edge set E.
i.e,
A graph H is said to be a subgraph of G if,

 the vertex set of graph H is a subset of the vertex set of graph G that is V(H) ⊆ V(G)
 the edge set of graph H is a subset of the edge set of graph G that is E(H) ⊆E(G)
 the vertex pairs of the edges of graph H are the same as the edges of graph G

A graph H is said to be an induced subgraph of G

 the vertex set of graph H is a subset of the vertex set of graph G that is V(H) ⊆ V(G)
 the edge set of graph H is a subset of the edge set of graph G that is E(H) ⊆E(G)
 the vertex pairs of the edges of graph H are the same as the edges of graph G

Introduction to Graph Coloring

Graph colouring refers to the problem of colouring vertices of a graph in such a way that
no two adjacent vertices have the same colour. This is also called the vertex colouring
problem. If colouring is done using at most m colors, it is called m-colouring.
Chromatic Number:
The minimum number of colours needed to colour a graph is called its chromatic
number. For example, the following can be coloured a minimum of 2 colours.

Bipartite Graph

Formal Definition:A graph G = (V, E) is said to be a bipartite graph if its vertex set V(G)
can be partitioned into two non-empty disjoint subsets. V1(G) and V2(G) in such a way that
each edge e of E(G) has one end in V1(G) and another end in V2(G).
 The partition V1 U V2 = V is called Bipartite of G.
 A complete bipartite graph, denoted as Km,n , is one where every vertex in the first set
(of size m) is connected to every vertex in the second set (of size n). It has a total of m+n
vertices and m×n edges.
A bipartite graph can be colored with two colors such that no two adjacent vertices share
the same color. This means we can divide the graph's vertices into two distinct sets where:
 All edges connect vertices from one set to vertices in the other set.
 No edges exist between vertices within the same set.
Example:

How to identify Bipartite Graph?

To identify whether a given graph is bipartite, you can use the following algorithm:
1. Choose any vertex in the graph and assign it to one of the two sets, say X.
2. Assign all of its neighbours to the other set, say Y.
3. For each vertex in set Y, assign all their unassigned neighbours to set X, and for
each vertex in set X, assign all their unassigned neighbours to set Y.
4. Check if any two adjacent vertices are in the same set. If yes, then the graph
is not bipartite. Otherwise, it is bipartite.

Example for not a bi partite Graph

Representations of Graph
Here are the two most common ways to represent a graph.
1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix Representation

An adjacency matrix is a way of representing a graph as a matrix of boolean (0's and 1's)
Let's assume there are n vertices in the graph So, create a 2D matrix adjMat[n][n] having
dimension n x n.

 If there is an edge from vertex i to j, mark adjMat[i][j] as 1.

 If there is no edge from vertex i to j, mark adjMat[i][j] as 0.

Representation of Undirected Graph as Adjacency Matrix:

The below figure shows an undirected graph. Initially, the entire Matrix is initialized to 0.
If there is an edge from source to destination, we insert 1 to both cases
(adjMat[source][destination] and adjMat[destination][source]) because we can go either
way.

Representation of Directed Graph as Adjacency Matrix:

The below figure shows a directed graph. Initially, the entire Matrix is initialized to 0. If
there is an edge from source to destination, we insert 1 for that
particular adjMat[source][destination].

Adjacency List Representation

 An array of Lists is used to store edges between two vertices.

 The size of array is equal to the number of vertices (i.e, n).
 Each index in this array represents a specific vertex in the graph.
  The entry at the index i of the array contains a linked list containing the vertices that
are adjacent to vertex i.
 Let's assume there are n vertices in the graph So, create an array of list of
size n as adjList[n].

 adjList[0] will have all the nodes which are connected (neighbour) to vertex 0.
 adjList[1] will have all the nodes which are connected (neighbour) to vertex 1
and so on.

Adjacency List For Undirected Graph

The below undirected graph has 3 vertices. So, an array of list will be created of size 3,
where each indices represent the vertices. Now, vertex 0 has two neighbours (i.e, 1 and 2).
So, insert vertex 1 and 2 at indices 0 of array. Similarly, For vertex 1, it has two neighbour
(i.e, 2 and 0) So, insert vertices 2 and 0 at indices 1 of array. Similarly, for vertex 2, insert
its neighbours in array of list.

Representation of Directed Graph as Adjacency list:

The below directed graph has 3 vertices. So, an array of list will be created of size 3, where
each indices represent the vertices. Now, vertex 0 has no neighbours. For vertex 1, it has
two neighbour (i.e, 0 and 2) So, insert vertices 0 and 2 at indices 1 of array. Similarly, for
vertex 2, insert its neighbours in array of list.

Walk
 A walk in a graph is a sequence of vertices and edges where both edges and vertices
can be repeated.
 The length of the walk refers to the number of edges covered in the sequence.
 A graph can contain multiple walks.

There are two key points to note about a walk:

1. Edges can be repeated.
2. Vertices can be repeated.
Here, 1-> 2-> 3-> 4-> 2-> 1-> 3 is a walk.

Types of Walks
There are two types of walks:
1. Open Walk
2. Closed Walk

Open Walk

 An open walk is a walk in which the starting and ending vertices are different.
 In other words, for a walk to be considered open, the origin and terminal vertices
must not be the same.
 The length of the walk must be greater than 0.
 In the above diagram:
1-> 2-> 3-> 4-> 5-> 3 is an open walk.

Closed Walk

 A closed walk occurs when the starting and ending vertices are identical, meaning
the walk starts and ends at the same vertex.
 For a walk to be classified as closed, the origin and terminal vertices must be the
same.
 Similar to an open walk, the length of the walk must be greater than 0.
 In the above diagram:
 1-> 2-> 3-> 4-> 5-> 3-> 1 is a closed walk.

Trail
A trail is an open walk in which no edge is repeated, though vertices may be repeated.
 Edges cannot be repeated
 Vertices can be repeated.
There are two types of trails:
1. Open Trail: A trail is considered an open trail if the starting and ending vertices
are different.
2. Closed Trail: A trail is a closed trail if the starting and ending vertices are the
same.
Here 1-> 3-> 8-> 6-> 3-> 2 is an open trail
Also 1-> 3-> 8-> 6-> 3-> 2-> 1 will be a closed trail
Circuit
1. A circuit can be described as a closed trail(starting and ending vertices are the
same) in graph theory, where no edge is repeated, but vertices can be repeated.
 Edges cannot be repeated.
 Vertices can be repeated.
Path
A path is a trail in which neither vertices nor edges are repeated.
 Vertices are not repeated.
 Edges are not repeated.

Here 6->8->3->1->2->4 is a Path

Cycle
A cycle in graph is a closed path, meaning that it starts and ends at the same vertex while
ensuring that no other vertices or edges are repeated.
  Edges cannot be repeated.
 Vertices cannot be repeated, except for the first and last vertex, which must be
the same.
Note: In graph theory, a circuit is a non-empty closed trail, meaning it's a sequence of
vertices and edges that starts and ends at the same vertex, with no repeated edges but
possibly repeated vertices. A cycle is a type of circuit where vertices are also not
repeated, with the only vertex repetition being the start and end vertex. Therefore, every
cycle is a circuit, but not every circuit is a cycle.

Category Edges Vertices

Walk Can be repeated Can be repeated

Trail Can’t be repeated Can be repeated

Circuit Can’t be repeated Can be repeated

Cycle Can’t be repeated Can’t be repeated, except

for first and last vertex
Path Can’t be repeated Can’t be repeated

Connected Graph.
A graph is said to be connected if there is a path between any two vertices in the graph.
In such graphs, it is possible to reach any vertex from any other vertex.

Disconnected Graph:
A graph where there's no path between at least one pair of vertices, resulting in two or more
isolated components.

Types of Connectivity

 Edge Connectivity (λ(G)):

 The smallest number of edges whose removal disconnects the graph or reduces it to
a single vertex.

 A single edge whose removal disconnects a graph is called a bridge.

 Vertex Connectivity (κ(G)):

The smallest number of vertices (a vertex cut) that must be removed to disconnect
the graph or reduce it to a single vertex. Κ is known as Kappa
 k-connected:
 A graph is k-vertex-connected if it remains connected even after removing any k-1
vertices. The vertex connectivity of a graph is the largest k for which it is k-
connected

Graph isomorphism

Note: It is a concept in graph theory that describes when two graphs are "the same" in
structure, even if they look different or have different labels.

Definition:
Two graphs G1=(V1,E1) and G2=(V2,E2) are isomorphic if there exists a bijection (one-to-
one and onto mapping) f:V1→V2 such that for any two vertices u,v∈V1,(u,v)∈E1 ⟺
(f(u),f(v))∈E2

In words: you can relabel the vertices of one graph so that it becomes exactly the other graph.

Key points:

 Isomorphic graphs have the same number of vertices and edges.

 They preserve adjacency (which vertices are connected).
 They preserve properties like degree sequence, connectivity, cycles, etc.

Example:

Here G and G 1 are Isomorphic to each other.

Here number of vertices and edges in each graph are the same
And also
Deg (V1) = 2 and Degree (V11) = 2

Deg (V2) = 2 and Degree (V21) = 2

Deg (V3) = 2 and Degree (V31) = 2

Deg (V4) = 2 and Degree (V41) = 2

Deg (V5) = 2 and Degree (V51) = 2

Handshaking Theorem/Handshaking Lemma/Sum of Degree Theorem:

Please refer notebook

Very important

Euler Path/Euler Trail

An Euler path is a path that uses every edge in the graph exactly once. It does not have to
return to starting vertex
Note: Vertices may or may not be repeated
Examples:

Euler Circuit/Euler Cycle/Euler Tour

Euler circuit is a circuit that uses every edge in a graph exactly once (with no repetition)
and it must start and end at same vertex

Eulerian Graph
An Eulerian graph is a connected graph that contains an Eulerian circuit, which is a path
that visits every edge exactly once and ends at the starting vertex

Euler Path - An Euler path is a path that uses every edge of a graph exactly
once. An Euler path starts and ends at different vertices.
Example 1:
Euler Path: C->B->A->C->D
Example 2:

Euler Path: A->B->C->A->D->C

Example 3: Euler path does not exist in the following Graph

Euler Circuit - An Euler circuit is a circuit that uses every edge of a graph
exactly once. An Euler circuit always starts and ends at the same vertex.
Example 1: B->A->E->B->C->D->E->B

Example 2: Euler Circuit does not exist in the following graph

 Euler’s Graph
A connected graph G is called an Euler graph, if there is a closed trail which
includes every edge of the graph G

Example 1:

Example 2:

Example 3: Not an Euler Graph

Determine whether the following graph has an Euler circuit or not
Example 1:

First find the degree of each vertices.

Here degree of all vertices are even, we can say that an Euler Circuit exists in this
Graph and the Euler Circuit is (C->B->A->F->E->D->C->F->C)

Example 2:

Here since the degree of the Vertex C(also Vertices E,G,A) has an odd degree, we
can say that an Euler Circuit does not exist in this Graph

Semi Euler Graph

If a connected graph contains an Euler trail but does not contain an Euler Circuit, then
such a graph is called as a Semi Euler Graph
Euler Trail : B->A->D->B->C->D
Question: Is it possible to draw Euler Circuit on the following graph?
(Yes)
B->A->G->F->E->C

Eulerian Circuit Theorem:

A connected graph G has an Eulerian circuit (a path that starts and ends at the same
vertex and traverses every edge exactly once) if and only if every vertex in G has an
even degree.
Proof

Assume G has an Euler circuit C. Let’s call that circuit a closed walk (trail)
C=v0,e1,v1,e2,v2,…,em,vm ,vm=v0, and every edge of G appears exactly once in this
walk.

Consider an arbitrary vertex v. In the walk C, each time the walk visits v, it must enter
along some edge and then exit along another (except at the start/end, but here start =
end so that vertex too must have that property). Thus the edges incident to v get paired
up: one for entering, one for leaving. Because the circuit is closed, even the “first” and
“last” visits pair up. So the total number of edges incident to v (i.e. the degree deg(v)
is a sum of such pairs, i.e. it’s even.

Hence every vertex in G has even degree.

Euler path (trail) condition

A connected graph G has an Euler path (but not necessarily a cycle) if and only if it
has exactly 0 or exactly 2 vertices of odd degree.

 If there are 0 odd-degree vertices, then there is an Euler circuit (so also a path).
 If there are 2 odd-degree vertices, the Euler path must start at one of the odd‐
degree vertices and end at the other.
 If there are more than 2 vertices of odd degree, then no Euler path or circuit
exists.

Thus combining these:

 Connected & all vertices even degree ⟺ Euler circuit exists.

 Connected & exactly two odd-degree vertices ⟺ Euler path exists but no
circuit.
 Connected & more than two odd-degree vertices ⟺ Neither a circuit nor a
path exists.

Hamiltonian Path /Semi Hamiltonian Path

Hamiltonian Path in a graph G is a path that visits every vertex of G exactly once
and it doesn't have to return to the starting vertex. It's an open path.

Example 1: Hamiltonian Path is: A->I->H->B->C->D->E->F->G

Note: here it is not necessary to go through every edge

Hamiltonian Cycle/Circuit

Hamiltonian Cycle or Circuit in a graph G is a cycle that visits every vertex
of G exactly once and returns to the starting vertex.
Example 1: 1->0->3->4->2->1
Example 2: 0->1->3->2->0

Example 3:

Hamiltonian graph –
A connected graph G is called Hamiltonian graph if there is a Hamiltonian
cycle which includes every vertex of G and the cycle is called Hamiltonian
cycle. Hamiltonian walk in graph G is a walk that passes through each vertex
exactly once.
Examples

Question 1:
State a Semi Hamiltonian path in the following Graph

(A->B->C->D->E)
Question 2:
Determine if this directed network is Hamiltonian, semi-Hamiltonian or neither.
This network is semi-Hamiltonian. The paths PUTSQR and QSUTPR visit each
vertex once. It is not possible to create such a path that starts and ends at the
same vertex, so the graph is not Hamiltonian.
Question 3: Which of the following are Semi Hamiltonian?

Travelling Salesman Problem

 In graph theory, the Traveling Salesman Problem (TSP) seeks the shortest
possible route(optimal solution) that visits every city (vertex) exactly once and
returns to the starting city, forming a Hamiltonian cycle.
 This route's cost, representing distance or time, is determined by the edge
weights in a weighted, complete graph where cities are vertices
Example: find the shortest possible route starting from City A that visits every other
cities exactly once and return to the city A
Here A->B->C->D->A is the shortest path
Question 1: find the shortest path from the following figure

The shortest Hamiltonian tour (starting and ending at A) has total length 26.

One optimal route is:

A→B→C→E→D→A

Cost breakdown:

 A→B=2
 B→C=7
 C→E=8
 E→D=5
 D→A=4
Total = 2 + 7 + 8 + 5 + 4 = 26

(There are three other equivalent tours with the same cost, e.g. A → B → D → E → C → A,
etc.)

Operations on Graph

 Graph operations modify a graph's structure, either by transforming a single graph

(unary operations) or by combining two or more graphs (binary operations).
  Common unary operations include adding/deleting vertices and edges, graph
contraction, and creating the complement graph.
 Binary operations include graph union, intersection, and various types of graph
products (Cartesian, tensor, strong, etc.).

Unary Operations (Single Graph)

These operations create a new graph from an existing one:

Complement Graph: A new graph with the same vertices, but edges exist between
two vertices if and only if they are not adjacent in the original graph.
Thus, the complement of a graph G ( V, E) is denoted as G′ ( V, E′), where:
 V is the set of vertices (remains unchanged),
 E′ is the set of edges in the complement graph.

Note:
The number of vertices in the complement of a graph remains unchanged. Only the
edges differ.


Properties of Complement of Graph
1. If E be the set of edges of graph G' then E(G')={ (u, v) | (u, v) ∉ E(G) }

2. Union of graph G and its complement G' will give a complete graph(Kn).
3. The intersection of two complement graphs has no edges, also known as null graph

4. If G is a disconnected graph then its complement G' would be a connected graph.

5. Order of a Graph and its Complement are Same. The order of the graph is the
number of vertices in it.

Self Complementary Graph

A self-complementary graph is a graph that is isomorphic to its own complement,
meaning its structure is identical to the graph formed by swapping its edges and non -
edges.
Examples of Self-Complementary Graphs:
 The four-vertex path graph.
 The five-vertex cycle graph
Transpose graph
In graph theory, the converse, transpose or reverse of a directed graph G is another
directed graph on the same set of vertices with all of the edges reversed compared to
the orientation of the corresponding edges in G. That is, if G contains an
edge (u, v) then the converse/transpose/reverse of G contains an edge (v, u) and vice
versa.

Binary Operations (Two or More Graphs) These operations combine two or more graphs
to form a new one:

Graph Union:

The new graph contains all vertices and all edges from both input graphs
Graph Intersection:

The new graph contains only the vertices and edges that are common to both input
graphs

Ring Sum of Graph(Symmetric Graph)

 In graph theory, the ring sum of two graphs, G1 and G2 (denoted G1 ⊕ G2), is a new
graph whose vertex set is the union of the two original vertex sets (V1∪V2), and
whose edge set is the symmetric difference of the two original edge sets (E1ΔE2).
 This means the ring sum includes edges that are in G1 or G2, but not in both.
Example 1:

Example 2:
Planar Graphs
A planar graph is a graph that can be embedded in the plane such that no edges intersect
except at their endpoints. In other words, it can be drawn on a flat surface without any
edges crossing

Face of planar Graph

A face of a planar embedding is a connected region of the plane.
Example 2:


Non Planar Planar
Note:
Example 1: Given a planar graph with 6 vertices and 9 edges, find the number of faces.

Solution:
Using Euler's formula:
V−E+F=2 ⟹ 6−9+F=2 ⟹ F=5

Kuratowski's Graphs

Kuratowski's graphs refer to two specific graphs, K5 and K3,3.
Kuratowski's 1st Graph with Diagram
A complete graph with 5 vertices is called Kuratowski's first graph. The graph is
generally denoted by K5.

Kuratowski's 2nd Graph with Diagram

A regular connected graph with 6 vertices and 9 edges is called Kuratowski's
second graph. The graph is generally denoted by K3,3

Chromatic Number of Kuratowski's Graphs

 The chromatic number of a graph is the minimum number of colors needed to
color the vertices of the graph such that no two adjacent vertices have the
same color.
 In other words, it is the smallest number of colors needed to color the vertices
of the graph so that no adjacent vertices have the same color.
 Chromatic number of Kuratowski's first non-plannar graphs (K5) is 5.
 Chromatic number of Kuratowski's second non-plannar graphs (K3,3) is 2.

Graph Homomorphism
Two graphs G1 and G2 are said to be homomorphic, if each of these graphs can be
obtained from the same graph 'G' by dividing some edges of G with more vertices.
Homomorphism Examples
Example 1 –Two homomorphic graphs are obtained from G by adding vertices to edges

Formal Definition: A graph homomorphism F from a graph G = (V, E) to a

graph G' = (V', E') is written as:
f : G --> G'
It is a mapping f: V --> V' from the vertex set of G to the vertex set of G' such that
{u, v} ∈ E ⇒ {f(u), f(v) ∈ E'

Example 2:

Divide the edge 'rs' into two edges by adding one vertex.

The graphs shown below are homomorphic to the first graph

Example 3: Example 4:

Example 5