GRAPH THEORY (BCS405B) 2024

MODULE-1
Introduction to Graphs: Introduction- Basic definition – Application of graphs – finite, infinite and bipartite
graphs – Incidence and Degree – Isolated vertex, pendant vertex and Null graph. Isomorphism, sub-graphs,
walks, paths and circuits, connected graphs, disconnected graphs and components.

Undirected Graph: Let 𝑉 be a nonempty set, and 𝐸 be a set of unordered pairs of elements of 𝑉.

Then the pair 𝐺( 𝑉, 𝐸 ) is called graph.

𝑉 is called set of vertices (or nodes) and 𝐸 , the set of edges (or arcs) .

Or 𝐺( 𝑉, 𝐸 ) is said to be a graph, if 𝑉 = {𝑣1 , 𝑣2 , ⋯ } is set of vertices, and 𝐸 = {𝑒1 , 𝑒2 , ⋯ } is set of edges

such that each edge 𝑒𝑘 is identified with unordered pair {𝑣𝑖 , 𝑣𝑗 } of vertices. Vertices 𝑣𝑖 , 𝑣𝑗 associated with
edge 𝑒𝑘 are called end vertices of edge 𝑒𝑘 .

Loop: An edge of the form (𝑎, 𝑎) or {𝑎, 𝑎} is called loop.

Loop free graph: A graph containing no loop.

Multigraph: If there exists two or more (in digraph, in the same direction) edges between any two vertices
(Parallel edges) then the graph is called multigraph.

Simple graph: A loop free graph without multiple edges is called simple graph otherwise general graph.

Null graph: A graph containing only vertices, no edge is called null graph.

Finite graph: A graph 𝐺( 𝑉, 𝐸 ) is said to be finite if |𝑉| and | 𝐸| are both finite, otherwise infinite graph.

Consider the graph 𝐺( 𝑉, 𝐸 ) with 𝑉 = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 } and 𝐸 = {𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 , 𝑒7 , 𝑒8 }

𝑣1 𝑒1 𝑣2
𝑒8

·
𝑒2 𝑒5
𝑒6 𝑣3
𝑒3

𝑣6
𝑒4 𝑒7
𝑣4 𝑣5

Fig: 1.1

Edges 𝑒2 and 𝑒3 are parallel edges. Edge 𝑒8 is a loop.

Bipartite graph: Suppose a simple graph G is such that its vertex set V is the union of its mutually disjoint non-
empty subsets V1 and V2 which are such that each edge in G joins a vertex in V1 and a vertex in V2 . Then G is
called bipartite graph. If E is the edge set of the graph, then the graph is denoted by G( V1 , V2 ; E). The set V1
and V2 are called bipartite (or partitions) of the vertex set V .

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

1
GRAPH THEORY (BCS405B) 2024

Complete bipartite graph: A bipartite graph G( V1 , V2 ; E) is called a complete bipartite, if there is an edge
between every vertex in V1 and every vertex in V2 , and denoted by 𝐾𝑚,𝑛

Incidence: When a vertex 𝑣 is an end vertex of an edge 𝑒, then 𝑣 and 𝑒 are said to be incident with each other.
The edge 𝑒 is incident on a vertex 𝑣, or the vertex 𝑣 is incident on an edge 𝑒.

Adjacency: Two nonparallel edges are said to be adjacent if they are incident on a common vertex.
Similarly, two vertices are said to be adjacent if there is an edge between them.

Degree of a vertex: Number of edges incident on a vertex 𝑣 (self-loop counted twice) is called degree of 𝑣
Or valency of 𝑣 and denoted by 𝑑(𝑣).

In fig1.1 graph, 𝑑(𝑣1 ) = 4, 𝑑(𝑣2 ) = 4, 𝑑(𝑣3 ) = 0, 𝑑(𝑣4 ) = 3, 𝑑(𝑣5 ) = 4, 𝑑(𝑣6 ) = 1.

⟹ ∑ dig(𝑣) = 16 = 2 × 8 = 2𝑒 , where e is the number of edges.

Isolated vertex: A vertex with degree zero. In fig1.1, 𝑣3 is isolated vertex.

Pendent vertex: A vertex with degree one. In fig1.1, 𝑣6 is pendent vertex.

Regular graph: A graph in which all the vertices are of equal degree is called a regular graph.
If all the vertices are of degree k, then we call k-regular graph.

Series edges: If the degree of a vertex 𝑣 is 2, then the two edges incident on 𝑣 are said to be in series.

Theorem: For an undirected graph, ∑ dig(𝑣) = 2𝑒 , and number of odd degree vertices is even.

Proof: Since each edge contribute 2 count to the ∑ dig(𝑣).

(One for one end vertex and another for another end vertex).

∴ ∑ dig(𝑣) = 2𝑒 .

Let 𝑉1 and 𝑉2 be the set of vertices of a graph with odd and even degrees respectively.

Then ∑ dig(𝑣) = 2𝑒 ⟹ ∑𝑣∈𝑉1 dig(𝑣) + ∑𝑣∈𝑉2 dig(𝑣) = 2𝑒.

⟹ ∑𝑣∈𝑉1 dig(𝑣) + 𝑒𝑣𝑒𝑛 = 𝑒𝑣𝑒𝑛 ⟹ ∑𝑣∈𝑉1 dig(𝑣) = 𝑒𝑣𝑒𝑛 .
Sum of the odd numbers is even ⟹ number of odd numbers is even.
Therefore the number of odd degree vertices is even.
2. If 𝐺 be an undirected graph with 𝑛 vertices and 𝑒 edges, let 𝛿 = min𝑣∈𝑉 {deg(𝑣)} and ∆= max𝑣∈𝑉 {deg(𝑣)},
2𝑒
then prove that 𝛿 ≤ 𝑛 ≤ ∆ .

Solution: For any vertex 𝑣𝑖 , 𝛿 ≤ deg(𝑣𝑖 ) ≤ ∆.

Taking summation, we get ∑𝑛𝑖=1 𝛿 ≤ ∑𝑛𝑖=1 𝑑(𝑣𝑖 ) ≤ ∑𝑛𝑖=1 ∆

2𝑒
⟹ 𝑛𝛿 ≤ 2𝑒 ≤ 𝑛∆. ⟹ 𝛿≤ 𝑛
≤∆.

3. Determine |𝑉| if

i) 𝐺 has 10 edges with 2 vertices of degree 4, and all others of degree 3.

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

2
GRAPH THEORY (BCS405B) 2024

ii) 𝐺 is 3-regular graph with 9 edges .

Solution: i) Let |𝑉| = 𝑛 . Given 𝑒 = 10, 2 vertices of degree 4, and (𝑛 − 2) vertices of degree 3.
∑ dig(𝑣) = 2𝑒 ⟹ 8 + 3(𝑛 − 2) = 20 ⟹ 3(𝑛 − 2) = 12 ⟹ 𝑛 = 6.
ii) Since each vertex is of degree3, ∑ dig(𝑣) = 2𝑒 ⟹ 3𝑛 = 18 ⟹ 𝑛 = 6 .
4. There is no simple graph with degree sequence 1, 1, 1, 2, 3, 4, 5. Give reason.
5. There is no simple connected graph with eight vertices having degree sequence 1, 1, 1, 2, 3, 4, 5 and 7. Why?
6. Give an example of connected graph with eight vertices having degree sequence 1, 1, 1, 2, 3, 4, 5 and 7.

Isomorphic Graphs:
Let G1 ( V1 , E1 ) and G2 (V2 , E2 ) be two undirected graphs. If there exists a function 𝑓 from V1 to V2 such that
i) 𝑓 is bijective. (One-one and onto).
ii) {𝑎, 𝑏} ∈ E1 ⟺ {𝑓(𝑎), 𝑓(𝑏)} ∈ E2 , for all 𝑎, 𝑏 ∈ V1 .
Then G1 and G2 are isomorphic graphs.
Or simply, Two graphs G1 ( V1 , E1 ) and G2 (V2 , E2 ) are said to be isomorphic if there is a one to one
correspondence between their vertices and between their edges such that the incidence relationship is preserved.
Example: Show that the following two graphs are isomorphic.
a v

u x

f b and

e c w

d y z

Solution: Consider the function 𝐹 from V1 to V2 such that 𝐹(a) = u, 𝐹(c) = v, 𝐹(e) = x,

𝐹(d) = y, 𝐹(b) = z , 𝐹(f) = w .

Clearly F is one to one and onto function.

{a, c} ∈ E1 ⟺ {𝐹(a), 𝐹(c)} = {u, v} ∈ E2 . {b, f} ∈ E1 ⟺ {𝐹(b), 𝐹(f)} = {z, w} ∈ E2 .

{a, e} ∈ E1 ⟺ {𝐹(a), 𝐹(e)} = {u, x} ∈ E2 . {b, e} ∈ E1 ⟺ {𝐹(b), 𝐹(e)} = {z, x} ∈ E2 .

{a, d} ∈ E1 ⟺ {𝐹(a), 𝐹(d)} = {u, y} ∈ E2 . {b, d} ∈ E1 ⟺ {𝐹(b), 𝐹(d)} = {z, y} ∈ E2 .

{c, f} ∈ E1 ⟺ {𝐹(c), 𝐹(f)} = {v, w} ∈ E2 . {c, e} ∈ E1 ⟺ {𝐹(c), 𝐹(e)} = {v, x} ∈ E2 .

{d, f} ∈ E1 ⟺ {𝐹(d), 𝐹(f)} = {y, w} ∈ E2 .

Therefore given two graphs are isomorphic.

2. Show that following two graphs are isomorphic.

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

3
GRAPH THEORY (BCS405B) 2024

𝑎 𝑒1 𝑣5
𝑒 𝑣4
𝑒3 𝑣3
4 2
5 1
𝑒2
𝑒4 𝑒6
𝑐
3
6

𝑑 𝑒5 𝑣2
𝑣1
𝑏

Solution: In both the graph there is only one pendent vertex, and one vertex with degree two, the function
𝑓 from V1 to V2 such that 𝑓(𝑏) = 𝑣2 , 𝑓(𝑒) = 𝑣5 . In first graph pendent vertex is adjacent to the vertex 𝑑,
therefore 𝑓(𝑑) = 𝑣4 . The remaining two vertices 𝑎, 𝑐 are adjacent to the vertices 𝑏, 𝑑 . Similarly vertices 𝑣1 , 𝑣3
are adjacent to the vertices 𝑣2 , 𝑣4 . ∴ 𝑓(𝑎) = 𝑣1 and 𝑓(𝑐) = 𝑣3 Or 𝑓(𝑎) = 𝑣3 and 𝑓(𝑐) = 𝑣1 .
Let 𝑓 be a function from V1 to V2 such that 𝑓(𝑎) = 𝑣1 , 𝑓(𝑏) = 𝑣2 , 𝑓(𝑐) = 𝑣3 , 𝑓(𝑑) = 𝑣4 and 𝑓(𝑒) = 𝑣5 .
Clearly 𝑓 is one-one and onto. The edges 1, 2, 3, 4, 5, 6 corresponds to 𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 respectively.
Therefore given two graphs are isomorphic.

Necessary conditions (but not sufficient) for two graphs to be isomorphic:

If two graphs are isomorphic, then
i) They have the same number of vertices.
ii) The same number of edges.
iii) An equal number of vertices with given degree. (Same degree sequence).

Consider the following two graphs: Both the graphs are having 6 vertices, 5 edges, one vertex of degree 3, two
vertices of degree 2, and 3 pendent vertices.

But in the first graph, two pendent vertices are adjacent to the vertex with degree 3 and in the second graph,
only one pendent vertex is adjacent to the degree 3 vertex. Hence there is no isomorphic function preserving
incidence relationship.

Subgraph: If 𝐺(𝑉, 𝐸) is a graph, then 𝐺1 ( 𝑉1 , 𝐸1 ) is called subgraph of 𝐺 if ∅ ≠ 𝑉1 ⊆ 𝑉 and 𝐸1 ⊆ 𝐸, where

each edge in 𝐸1 is incident with vertices in 𝑉1.

Clearly every graph is its own subgraph. Subgraph of a subgraph of G is subgraph of G.

Spanning Subgraph: If 𝑉1 = 𝑉 , then 𝐺1 is called spanning subgraph of 𝐺 .

Subgraph containing all the vertices of 𝐺 is called spanning subgraph of 𝐺.

Induced subgraph: Let 𝐺(𝑉, 𝐸) be a graph and 𝑈 is any nonempty subset of 𝑉 . The subgraph of 𝐺
induced by 𝑈 is the subgraph whose vertex set is U and contains all the edges of G which
are incident with the vertices of U and denoted by < 𝑈 >.

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

4
GRAPH THEORY (BCS405B) 2024

Walk: Let 𝑥 , 𝑦 be (not necessarily distinct) vertices of a graph 𝐺( 𝑉, 𝐸 ). 𝑥­𝑦 walk in G is a finite alternating
sequence 𝑥 = 𝑥0 , 𝑒1 , 𝑥1 , 𝑒2 , 𝑥2 , 𝑒3 ⋯ ⋯ , 𝑒𝑛−1 𝑥𝑛−1 , 𝑒𝑛 𝑥𝑛 = 𝑦 of vertices and edges from G starting at
vertex 𝑥 and ending at 𝑦 and involving 𝑛 distinct edges with 𝑒𝑖 = {𝑥𝑖−1 , 𝑥𝑖 } , where 1 ≤ 𝑖 ≤ 𝑛.
Number of edges present in the walk is called length of the walk.
If 𝑥 = 𝑦 , then 𝑥­𝑦 walk is called closed walk. If 𝑥 ≠ 𝑦 , then 𝑥­𝑦 walk is called open walk.

Path: If no vertex in 𝑥­𝑦 open walk appears more than once then, the 𝑥­𝑦 walk is called path.

Circuit: If no vertices in a closed walk appears more than once then the closed walk is called circuit.
Connected graph: A graph is said to be connected, if there is at least one path between every pair of vertices of
a graph. A graph is not connected is called disconnected graph.
If a graph G (V, E) is disconnected, then the vertex set V can be partitioned into at least two subsetsV1 & V2 such
that there is no edge in E of the form {𝑥, 𝑦} where 𝑥 ∈ V1 and 𝑦 ∈ V2 .
Component: Maximal connected sub graph of a graph.
For any graph G = ( V, E ) , number of components of G is denoted by 𝜅(𝐺).

Therefore if, 𝜅(𝐺) = 1, then graph is connected, and if 𝜅(𝐺) ≥ 2, then graph is disconnected.

Complete Graph (𝑲𝒏 ): Complete graph on n vertices is simple graph with one and only one edge between
every pair of vertices.

Complement of a graph: Let 𝐺 be a simple graph on 𝑛 vertices. The complement of 𝐺 denoted by 𝐆 is the
subgraph of 𝐾𝑛 consisting of the 𝑛 vertices of 𝐺 and all edges that are not in G.

Exercise:

1. Find the number of edges in 𝐾𝑛 and 𝐾𝑚,𝑛 .

𝐾𝑛 is a complete graph and hence there is one and only one edge between any two vertices.
𝑛(𝑛−1)
Therefore number of edges is number of selection of 2 vertices from n vertices ∴ 𝑒 = 𝑛𝑐2 = .
2
𝑛(𝑛−1)
Or, in 𝐾𝑛 every vertices is of degree (𝑛 − 1) .Therefore 2𝑒 = ∑ dig(𝑣) = 𝑛(𝑛 − 1) ∴ 𝑒 = .
2

In 𝐾𝑚,𝑛 , from each of m vertices of one vertex set there are n edges to the n vertices of another vertex set.

Therefore number of edges in 𝐾𝑚,𝑛 is 𝑒 = 𝑚𝑛. and the number of vertices is 𝑚 + 𝑛.

2. If G is a graph on n vertices, for 𝑛 ≥ 2, and G is not connected, prove that 𝐺̅ is connected.

Proof: If G = (V, E) is not connected, then the vertex set V can be partitioned into at least two subsets V1, V2
such that there is no edge in E of the form {x, y} where x ∈ V1 and y ∈ V2. But the edge {x, y} is in 𝐺̅ for any
vertices x ∈ V1 and y ∈ V2.

To show 𝐺̅ is connected. Consider any two vertices a, b of 𝐺̅ . If a ∈ V1 and b ∈ V2 or b ∈ V1 and a ∈ V2 , then

the edge {a, b} is in 𝐺̅ , and hence there is a path in 𝐺̅ between a and b. If a and b both are in V1 (or in V2). Then
{a, c}, {c, b} is a-b path in 𝐺̅ , where c ∈ V2 (or c ∈ V1). Therefore 𝐺̅ is connected.

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

5
GRAPH THEORY (BCS405B) 2024

3. Let G be a loop-free connected undirected graph containing more than one vertex. Prove that G contains at
least two vertices of same degree.

Proof: Let n be the number of vertices of G. Then a vertex v can be adjacent to at most n-1 vertices of G and at
least one vertex. Therefore 1 ≤ deg(𝑣) ≤ 𝑛 − 1. Let degrees {1, 2, 3, … . . 𝑛 − 1 } be 𝑛 − 1 pigeonholes and 𝑛
vertices be 𝑛 pigeons. Then by pigeonhole principle at least one pigeonhole contains more than one pigeons.
That is at least two vertices are of same degrees.

4. Draw all non-isomorphic subgraphs of 𝐾4 .

Therefore given two graphs are isomorphic.

5. Show that the following two graphs are isomorphic.

i) and

ii) and

iii) and

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

6
GRAPH THEORY (BCS405B) 2024

iv) and

6. Show that the following graphs are not isomorphic.

i) and

ii)

and

7. Define self-complimentary graph, give an example of 4 vertices and 5 vertices self-complimentary graph.

8. Find all spanning sub graphs. How many of them are connected. How many are spanning trees (acyclic &
connected).

b c d e

9. Find the number of paths of length 2 in the graph

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

7
GRAPH THEORY (BCS405B) 2024

10. Let 𝑉 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓}. Draw three nonisomorphic loop free undirected graphs with deg(𝑎) = 3,

deg(𝑏) = deg(𝑐) = 2 and deg(𝑑) = deg(𝑒) = deg(𝑓) = 1 .

11. Find the i) number of spanning subgraphs, ii) number of connected spanning subgraphs

iii) Number of spanning subgraphs with 𝑎 as isolated vertex.

g e

h i

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

8