OE2C10: Graph Theory

Dr. Durgesh Singh

Assistant Professor
Department of Computer Science & Engineering
PDPM, IIITDM Jabalpur (M.P.) – 482005
Syllabus
 Module 1: Introduction, Types of Graphs, Subgraphs, Basics of walks, Paths, Cycles, and Trails,
Complement of a graph, Eulerian and Hamiltonian Graph, Bipartite Graphs, Diameter of a graph,
Isomorphic graphs.
 Module 2: Acyclic graphs, Forests, shortest paths algorithms, Matchings and Covers, Maximum
Matching in Bipartite Graph, Hall's Theorem and Konig's Theorem, Independent Set and Edge Cover.
 Module 3:Theorem, Stable Matching, Gale-Shapley Algorithm, Graph Connectivity, 2-Connected
Graphs, Subdivision of an edge, 2-edge-connected graphs, Problems Related to Graphs Connectivity,
Flow Network and Residual Network.
 Module 4: Augmenting Path, Augmenting Path Algorithm, Max-Flow and Min-Cut, Max-Flow and Min-
Cut Theorem, Vertex Colouring, Chromatic Number and Max. Degree, Edge Colouring, Planar Graphs
and Euler's Formula, Characterization Of Planar Graphs, Colouring of Planar Graphs.
Text/Reference Books & Notes
Course Books:
 D. B. West, Introduction to Graph Theory, Pearson
 N. Deo, Graph Theory with applications to computer science, PHI Learning Private
Limited
Reference Book:
 Thomas H Cormen, Charles E Leiserson, Ronald L. Rivest, and Cliff Stein, Introduction
to Algorithms, MIT Press.
Evaluation Scheme
 Quiz I : 15 Marks
 Mid term : 30 Marks
 Quiz II : 10 Marks + 5 Marks (Attendance)
 End term: 40 Marks
 Attendance Marks
If Attendance >=95% (5 Marks)
Else if Attendance >=90% (3 Marks)
Else if Attendance > =85% (2 Marks)
Else if Attendance > =80% (1 Marks)
Else if Attendance > =75% (0 Marks)
Else “Not allowed in end sem exam and Quiz II”
Introduction
 Graph theory is the study about graphs and their properties.
Goal: How to apply graph theory to real world problems.
Example: Airlines Problems
There is a five cities which are called A, B, C, D, and E. And there are
six round flights between them (A—B, A—C, A—E, B—D, C—D, C—E )
Q1: Is there a direct flight from A to D?
Q2: Can you fly from A to D with one stop? with two stops?
Airlines Problems …
The Königsberg Seven Bridge Problem(1736)
 Königsberg is a city on the Pregel river in Prussia.
 The city occupied two islands plus areas on both banks

Problem:
• Whether a person could leave home, cross every bridge exactly once,
and return home?
The Königsberg Seven Bridge as a Graph
Some more applications:
 Social networks. The "nodes" are people, and the "edges" are
friendships.
 College applications. Here, the nodes are both people and colleges,
and there's a edge between a person and a college if the person
applied to a college; there are no edges between two people or two
colleges. (This form of a graph is called bipartite because it has two
distinct sets of nodes.)
Some more applications...
 The world wide web. The nodes are web pages, and the edges are
links between the web pages.
 The "shortest path" problem: What's the quickest way to get from
one node to another?
 Modeling airline routes
 Modeling road networks
Graph
 A graph G=(V, E) is a collection of sets V and E where V is the set of
vertices (or nodes) and E is the set of edges.
 An edge is a line or arc connecting two vertices and it is denoted by a
pair(v1, v2) where v1, v2 belongs to the set of vertices V.
Note:
❖ The order of a graph G, written n (G ), is the number of vertices in G.

i.e. n(G) = | V |
❖ The size of a graph G, written e (G ), is the number of edges in G. i.e.
e(G) = | E |
Example

n(G) = ? ; e(G) = ?

n(G) = 4; e(G) = 7
Loop, Parallel edges
 Parallel Edges: If two vertices are connected with more than one edge
than such edges are called parallel edges.
 Loop: An edge of a graph which join a vertex to itself is called loop
or a self-loop.

parallel
edges
loop
Simple Graph
 Simple graph: A graph has no loops or parallel edges

Parallel
edges loop

It is not simple. It is a simple graph.

Note: Parallel edge is also known as Multiple edge.

Multi Graph
 A graph having no self loops but having parallel edge(s) in it is called
as a multi graph.
Pseudo Graph
 A graph having parallel edges as well as self loop(s) in it is called as
a pseudo graph.
Adjacent, neighbors
 Two vertices are adjacent (or neighbors ) if they are the endpoints of
an edge.
 Example:
A and B are adjacent.
 A and D are not adjacent.
Vocabulary
Null graph
 Null graph: the graph whose edge set are empty.
 In other words, a null graph does not contain any edges in it
Trivial graph
 A graph having only one vertex in it is called as a trivial graph.
 It is the smallest possible graph
Finite Graph
 Finite graph: an graph whose vertex set and edge set are finite.
Infinite Graph
 A graph consisting of infinite number of vertices or edges is called as
an infinite graph.
Subgraph
 A subgraph of a graph G is a graph H such that:
 V(H)  V(G) and E(H)  E(G) and
 The assignment of endpoints to edges in H is the same as in G.

Example: H1, H2, and H3 are subgraphs of G

Walk
 A walk in a graph G= (V, E) is an alternate sequence of vertices and
edges 𝑣0 𝑒1 𝑣1 𝑒2 𝑣2 … . . 𝑣𝑛−1 𝑒𝑛−1 𝑣𝑛 , beginning and ending with
vertices such that 𝑒𝑖 =(𝑣𝑖−1 , 𝑣𝑖 ).
 This walk joints 𝑣0 and 𝑣𝑛 , and called a (𝑣0 , 𝑣𝑛 ) walk

 A walk is closed if 𝑣0 = 𝑣𝑛 ; otherwise it is called an open walk.

 The total number of edges covered in a walk is called as Length of

the Walk.
Note: Both vertices and edges can repeat in a walk whether it is an
open walk or a closed walk
Example

(v1, v2) walk: v1 e4 v3 e6 v4 e7 v5 e7 v4 e2 v2

Trail, Circuit
 A walk is a trail if the edges are distinct.
 The total number of edges covered in a trail is called as Length of the

trail
 A trail is closed if 𝑣0 = 𝑣𝑛 ; otherwise, it is called an open trail.

 A closed trail is also called circuit.

Note: Vertices may repeat but edges are not allowed to repeat.
Example

(v4, v5) trail: V4 e7 v1 e1 v2 e2 v3 e3 v4 e4 v5

Path, Cycle
 A walk is a path if the vertices are distinct.
 In path, if 𝑣0 = 𝑣𝑛 then it is called closed path or cycle otherwise it is
called open path.
 The total number of edges covered in a path is called as Length of

the path
Note:
1. Every path is a trail, but every trail need not be a path.
2. Every cycle is a circuit, but every circuit need not be a cycle.
Example

(v1, v5) path: v1 e1v2 e2 v3 e3 v4 e4 v5

Undirected Graph
 A graph in which all the edges are undirected is called as an
Undirected graph.
 In other words, edges of an undirected graph do not contain any
direction.
Directed Graph
 A graph in which all the edges are directed is called as a directed
graph.
 In other words, all the edges of a directed graph contain some
direction.
 Directed graphs are also called as digraphs.
Degree of Vertices
 The degree of a vertex v in graph G denoted by d(v), is the number
of edges of G incident to v except that each loop at v counts twice.

Note: When a vertex v is an end vertex of some edge e, v and e are

said to be incident with (on or to) each other.
Degree of Vertices
 Maximum Degree: The Maximum Degree of a graph G denoted by
Δ(G), is the degree of the vertex with the greatest number of edges
incident to it.
 Minimum Degree: The Minimum Degree of G denoted by δ(G), is the
degree of the vertex with the least number of edges incident to it.
 Degree of vertex can be considered under two cases of graphs −
 Undirected Graph
 Directed Graph
Degree of Vertex in an Undirected Graph
 An isolated vertex is a vertex with degree zero; that is, a vertex that
is not an endpoint of any edge.
 A leaf vertex (also pendant vertex) is a vertex with degree one.

d(a) = 2, as there are 2 edges meeting at vertex 'a'.

d(b) = 3, as there are 3 edges meeting at vertex 'b'.
d(c) = 1, as there is 1 edge formed at vertex 'c ‘.
So 'c' is a pendent vertex.
d(d) = 2, as there are 2 edges meeting at vertex 'd'.
d(e) = 0, as there are 0 edges formed at vertex 'e'.
So 'e' is an isolated vertex.

Δ(G) = 3, δ(G) = 0
Degree of Vertex in a Directed Graph
 In a directed graph, one can distinguish the outdegree (number of
outgoing edges), denoted d+(v), from the indegree (number of
incoming edges), denoted d−(v).
 The degree of any vertex v is the sum of indegree and outdegree of
v.
d(v) = d+(v) + d−(v)
 A source vertex is a vertex with indegree zero.
 A sink vertex is a vertex with outdegree zero.
 An isolated vertex in a digraph is a vertex in which the in-degree and
the out-degree are both equal to zero.
 A vertex v in a digraph is called pendant if it is of degree one, that is,
if d+(v) + d−(v) =1
Example
Handshake Theorem (Degree-Sum Formula)
Theorem: The sum of the degrees of all vertices in G is twice the
number of edges in G. Let a graph G with e edges has vertices 𝑣1 ,
𝑣2 , …., 𝑣𝑛 , then
σ𝑛𝑖=1 𝑑(𝑣𝑖 ) = 2e
Proof:
Summing the degrees counts each edge twice,
 Because each edge has two ends and contributes to the degree at each
endpoint.
 That is why this is the degree sum is equal to 2e.
 2𝑒
 Note: In a graph G, the average degree is , and
𝑛
2𝑒
Hence , δ(G) ≤ ≤ Δ(G)
𝑛
Theorem
 In any graph G, the number of vertices of odd degree in a graph is
always even.
 Proof:

 Apply Handshake Theorem (Degree-Sum Formula)

Theorem
 In any graph G, the number of vertices of odd degree in a graph is
always even.
 Proof: Let a graph G with e edges has vertices 𝑣1 , 𝑣2 , …., 𝑣𝑛 , then,

 σ𝑛𝑖=1 𝑑(𝑣𝑖 ) = 2e …………………………(1)

 Let 𝑣1 , 𝑣2 , …., 𝑣𝑡 are odd degree vertices and 𝑣𝑡+1 , 𝑣𝑡+2 , …., 𝑣𝑛
are even degree vertices, then from eq(1),
𝑑(𝑣1 ) + 𝑑(𝑣2 ) + … + 𝑑 𝑣𝑡 + 𝑑(𝑣𝑡+1 )+ ….+𝑑(𝑣𝑛 ) = 2e ……..(2)
From eq. (2), we get
𝑑(𝑣1 ) + 𝑑(𝑣2 ) + … + 𝑑 𝑣𝑡 = 2e – (𝑑(𝑣𝑡+1 )+ ….+𝑑(𝑣𝑛 ) ) …….(3)
Since the RHS in Eq. (3), the first expression (2e) is even, and the second
expression on the RHS is even (being a sum of even numbers), then the
LHS must be even i.e.
𝑑(𝑣1 ) + 𝑑(𝑣2 ) + … + 𝑑 𝑣𝑡 = an even number
Here, 𝑑 𝑣1 , 𝑑 𝑣2 , … , 𝑑 𝑣𝑡 are all odd number but its sum is even,
So, t (number of odd vertices) must be even
Theorem
 In any digraph G the sum of all in-degrees is equal to the sum of all
out-degrees, each sum being equal to the number of edges in G; that
is σ𝑛𝑖=1 d+(𝑣𝑖 ) = σ𝑛𝑖=1 d−(𝑣𝑖 ) = e
Proof: The first sum counts the number of outgoing edges over all vertices
and the second sum counts the number of incoming edges over all vertices.
It follows that both sums equal the number of edges in the graph.
Complete Graph
 A graph is complete if every pair of vertices are adjacent.
OR
(A graph is complete is there exists an edge between every
pair of vertices.)
 A complete graph with ‘n’ vertices is denoted by 𝐾𝑛 .

 A complete graph of ‘n’ vertices contains exactly edges

Example

𝐾2 𝐾3 𝐾4
𝐾5
Regular Graph
 A graph in which all vertices are of equal degree is called a regular
graph
 If all the vertices in a graph are of degree ‘k’, then it is called as a “k-
regular graph”.

Note: A complete graph with n vertices is an (n-1) regular graph

Cycle Graph
 A simple graph of ‘n’ vertices (n>=3) and n edges forming a cycle of
length ‘n’ is called as a cycle graph.
 It is denoted by 𝐶𝑛
 In any 𝐶𝑛 , if vertices are 𝑣1 , 𝑣2 , …., 𝑣𝑛 then n edges will be (𝑣1 ,
𝑣2 ), (𝑣2 , 𝑣3 ),….,(𝑣𝑛−1 , 𝑣𝑛 ) and (𝑣𝑛 , 𝑣1 ).
 In a cycle graph, all the vertices are of degree 2.
Examples
Cyclic Graph
 A graph containing at least one cycle in it is called as a cyclic graph.
Acyclic Graph
 A graph not containing any cycle in it is called as an acyclic graph.
Connected and Disconnected Graph
 Connected: A graph is connected if every pair of vertices are joined
by a path.
 Disconnected: A graph in which there does not exist any path between
at least one pair of vertices.
 Its maximal connected subgraphs are called components.
Example:
◼ H1 and H2 are connected.
◼ H3 is disconnected.
Connected Components
A connected component is a maximal subgraph in which all nodes are
reachable from every other.
Note: If a graph is disconnected then it has at least 2 components
 Theorem: Every graph with n vertices and k edges has at least n-k
components
Proof:
 An n-vertex graph with no edges has n components
 Each edge added reduces this by at most 1

 If k edges are added, then the number of components is at least n-k

Examples
Theorem: Let a graph G =(V, E) of order n. If d(u) +d(v) ≥ n-1 for every
two non adjacent vertices u and v of G, then G is connected.
Proof: We need to prove that every two vertices of G are connected by
a path.
Let x, y 𝜖 V(G) , if(x,y) 𝜖 E(G), then x and y are adjacent
Assume that (x, y) 𝜖 E(G)
Given: d(x) +d(y) ≥ n-1
Let n = 6
Then d(x) + d(y) ≥ 5
Method1: According to Pigeonhole Principle : if n items are put into m
containers, with n >m, then at least one container must contain more than
one item.
Here assume edges are items and vertices are containers.
Method 2

Let d(x) =3 and d(y) = 2 this implies there must be a vertex 𝑣𝑖 that is
adjacent to both x and y.
Here, x 𝑣𝑖 y is a path of length 2
so, G is connected
Theorem
Theorem: If G is a graph of order n with δ(G) ≥ 𝑛−1
2
, then G is
connected.
Proof:
Theorem: If G is a graph of order n with δ(G) ≥ 𝑛−1
2
, then G is
connected.
Proof: We need to prove that every two vertices of G are connected by
a path.
For every two non adjacent vertices u and v
d(u) ≥ 𝑛−1
2
, and d(u) ≥ 𝑛−1
2
(because δ(G) ≥ 𝑛−1
2
)
𝑛−1 𝑛−1
So, d(u) +d(v) ≥ + = n-1
2 2
→ G is connected
Complement of a Graph (𝐺ҧ )
 A complement of a graph G, denoted by 𝐺,ҧ has the same set of
vertices as G, but two vertices are adjacent in 𝐺ҧ iff they are not
adjacent in G.
Relationship Between G & 𝐺ҧ
 Number of vertices in G = Number of vertices in 𝐺ҧ

 The sum of total number of edges in G and 𝐺ҧ is equal to the total

number of edges in a complete graph.
Example
Q : A simple graph G has 10 vertices and 21 edges. Find total number
of edges in its complement graph 𝐺.ҧ
Sol:
Theorem: If G is disconnected graph, then 𝐺ҧ is
connected
Proof: If u, v 𝜖 V(G) , we must find a path in 𝐺ҧ joining u and v.
Case I: Let u and v are in two different components on G.

Then, u and v are not adjacent in G

Hence, u and v are adjacent in 𝐺ҧ (By Definition of complement of
graph)
Case II: Let u and v are in the same component
-- then u and v may or may not be adjacent in G.
Let w be a vertex in another component of G.
→ w is not adjacent to both u and v in G
So, w is adjacent to both u and v in 𝐺ҧ (By Definition of complement of
graph)
Thus, there is a path u w v joining u and v in 𝐺ҧ
So, 𝑮ഥ is connected
 Euler Graph (or Eulerian Graph)
 An Euler Graph is a connected graph that contains an Euler Circuit.
 Euler Trail: Euler trail is also known as Euler path or Euler Walk.

If there exists a trail in the connected graph that contains all the edges
of the graph, then that trail is called as an Euler trail.
OR
If there exists a walk in the connected graph that visits every edge of
the graph exactly once with or without repeating the vertices, then such
a walk is called as an Euler walk.
Euler Circuit
 Euler circuit is also known as Euler Cycle
 If there exists a circuit in the connected graph that contains all the
edges of the graph, then that circuit is called as an Euler circuit. OR
 If there exists a walk in the connected graph that starts and ends at
the same vertex and visits every edge of the graph exactly once with
or without repeating the vertices, then such a walk is called as an Euler
circuit. OR
 An Euler trail that starts and ends at the same vertex is called as an
Euler circuit. OR
 A closed Euler trail is called as an Euler circuit.
Theorem
 Statement: A connected graph or multigaph G is Eulerian if and only
if every vertex has even degree.
Examples:

Whether the given graph

contains Euler Trail or not?
Examples:

Whether the given graph

contains Euler circuit or
not?
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 C D B A D

Note: If the number of vertices with odd degree are at most 2, then graph
contains an Euler trail otherwise not.
A connected graph or multigaph G is Eulerian if
and only if every vertex has even degree.
Proof: (→)
Assume G is a connected Eulerian graph.
Let w: u – u be an Eular Circuit
Let v ≠ u be a vertex that occurs k times in Euler Circuit w.

Every time an edge arrives at v, another edge exits from v,

So, d(v)= 2k (an even integer)
Also, d(u) is even, since w starts and ends at u.

Thus if G is an Euler graph, the degree of every vertex is even.

( ) To prove the sufficiency of the condition, assume G is a connected
graph such that d(v) is even for all V(G)
Then select a vertex and form an Eulerian trail starting that vertex.
(Apply Fleury’s Algorithm)
Fleury’s Algorithm
 Fleury’s algorithm is used to find a Euler Path or a Euler Circuit in a
connected graph.
 Bridge: Bridge is an edge such that removing it from the graph
disconnects the graph into 2 connected components. A bridge can
never be part of a cycle.
 When there are two edges, one is bridge, another one is non-bridge,
we have to choose non-bridge at first.
Fleury’s Algorithm…
 In this algorithm, starting from one vertex, it tries to move other
adjacent vertices.
 At each step, we move across an edge, ensuring that its deletion does
not result in more than one component, unless we have no choice.
 At the end of algorithm, there are no edges left and the sequence of
edges we moved across form a Eulerian trail.
 If the graph contains an Euler Circuit, then the path will end at the
starting vertex.
(→)Let a graph G in which every vertex has even degree
 Corollary: A connected multi-graph G is semi-Eulerian if and only if
there are exactly 2 vertices of odd degree.
Hamiltonian Graph
 A Hamiltonian cycle (or Hamiltonian circuit) in the connected graph G
is a Cycle that contains all the vertices of the graph.
 A Hamiltonian path (or spanning path) in the connected graph G is a
a Path that contains all the vertices of the graph.
 A closed Hamiltonian path is called as a Hamiltonian cycle.

 A graph is a Hamiltonian graph if it contains a Hamiltonian cycle

Note: In Hamiltonian path, all the edges may or may not be covered but
edges must not repeat.
examples
 Cycle graph 𝐶𝑛 is Hamiltonian for any n ≥ 3

 Complete Graph 𝐾𝑛 is Hamiltonian for any n ≥ 3.

 A Hamiltonian cycle in a graph of n vertices consists of exactly n
edges.
 The length of a Hamiltonian path (if it exists) in a connected graph of
n vertices is n-1.
 In considering the existence of a Hamiltonian cycle (or path), we need
only consider simple graphs.
 Thisis because a Hamiltonian cycle (or path) traverses every vertex exactly
once. Hence it cannot include a self-loop or a set of parallel edges. Thus a
general graph may be made simple by removing parallel edges and self-
loops before looking for a Hamiltonian cycle in it.
 The question: What is a necessary and sufficient condition for a
connected graph G to have a Hamiltonian circuit? (NP complete
Problem)
 This problem, first posed by the famous Irish mathematician Sir William
Rowan Hamilton in 1859, is still unsolved.
 There is no known criterion we can apply to determine the existence of
a Hamiltonian cycle in general.
Maximal non Hamiltonian Graph
 A simple graph G is called maximal non- Hamiltonian graph if it is not
Hamiltonian and the addition of an edge between any two
nonadjacent vertices of it forms a Hamiltonian graph.
 Example:
Theorem
 Dirac's Theorem - If G is a simple graph with n vertices, where n ≥ 3
If deg(v) ≥ n/2 for each vertex v, then the graph G is Hamiltonian
graph.
 Dirac's Theorem provides only sufficient condition for a connected
simple graph to have Hamiltonian cycle
 Do not provide the necessary condition for the existence of a
Hamiltonian cycle
Example
 C4, C5, C6
Ore’s Theorem:
 If G is a simple graph with n vertices, where n ≥ 3 if deg(x) + deg(y)
≥ n for each pair of non-adjacent vertices x and y, then the graph G
is Hamiltonian graph.
Bipartite Graph
 A bipartite graph is a graph whose vertices can be divided into two
parts A and B such that every edge connects a vertex in A to a
vertex in B.
Let G=(V, E) be bipartite. Then, V=A∪B such that A∩B=∅ and that all
edges e∈ E are such that e is of the form {a, b} where a ∈A and b ∈B.
Complete Bipartite Graph
 A bipartite graph G=(A ∪ B, E) , where every vertex of set A is joined
to every vertex of set B is called as complete bipartite graph.
 If A contains m vertices, B contains n
vertices then the complete bipartite is denoted by Km, n.
Example:
 Is the following graph a bipartite graph?