JIE Lecture Notes

MMC102
Discrete Mathematics and Graph Theory
Module 3- Introduction to Graphs

Prepared by

Dr. Shantha Kumari. K

AJIET, Mangaluru
Contents

IE T
Introduction to Graphs

3.1

3.2

3.3

3.4

3.5

3.6

3.7

3.8
Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Edges and Their Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Graph Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Simple Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Konigsberg Bridge Problem . . . . . . . . . . . . . . . . . . . . . . . . . . .

Incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Adjacency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Degree of a Vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3

3.9 Handshaking Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.10 Corollary (Vertices of Odd Degree) . . . . . . . . . . . . . . . . . . . . . . . . 8

AJ
3.11 Isolated Vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.12 Pendant (End) Vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.13 Edges in Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.14 Null Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.15 Regular Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.16 Complete Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.17 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.18 Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.18.1 Necessary Conditions for Isomorphism . . . . . . . . . . . . . . . . . 16

3.19 Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1
Lecture Notes - MMC102 Page 2

3.19.1 Properties of a Walk . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.19.2 Open and Closed Walks . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.19.3 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.19.4 Length of a Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

IE T
3.19.5 Degrees of Vertices in a Path . . . . . . . . . . . . . . . . . . . . . . . 19

3.19.6 Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.20 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.20.1 Edge-Disjoint Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.20.2 Vertex-Disjoint Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . 21

3.21 Connected Graphs, Disconnected Graphs, and Components . . . . . . . . . . . 22

AJ

Dr. Shantha Kumari K. AJIET, Mangalore

Module 3

IE T
Introduction to Graphs

3.1 Graph

A graph is an ordered pair

where:
G = (V, E),

• V = {v1 , v2 , . . .} is a nonempty set whose elements are called vertices, and

• E = {e1 , e2 , . . .} is a set whose elements are called edges.

Each edge ek ∈ E is associated with an unordered pair (vi , vj ) of vertices.

AJ
For a graph G = (V, E), the number of vertices is called the order of the graph and is denoted
by |V |. The number of edges is called the size of the graph and is denoted by |E|.

3.2 Edges and Their Properties

• The vertices vi and vj associated with an edge ek are called the end vertices of the edge
ek .

• An edge having the same vertex as both its end vertices is called a self-loop (or simply a
loop).

• If more than one edge is associated with the same pair of vertices, such edges are called
parallel edges.

3
Lecture Notes - MMC102 Page 4

3.3 Graph Representation

The most common representation of a graph is by means of a diagram:

• Vertices are represented as points.

IE T
• Edges are represented as line segments joining their end vertices.

Example:

3.4 Simple Graph

A graph is called a simple graph if it contains no self-loops and no parallel edges. Thus, in a
simple graph, at most one edge exists between any pair of distinct vertices.
Example: Consider the graph shown in the following figure.
AJ
The graph contains four vertices and six edges. There are no self-loops and no parallel edges.
Therefore, it is a simple graph.

3.5 Konigsberg Bridge Problem

The Königsberg bridge problem is one of the most famous and historically significant problems
in graph theory. It was solved by the Swiss mathematician Leonhard Euler (1707–1783) in the

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 5

year 1736. Euler’s work on this problem led to the publication of the first paper in graph theory
and is widely regarded as marking the origin of the subject.

The city of Königsberg was divided by the Pregel River into four distinct land areas, denoted by
A, B, C, and D. Among these, C and D were islands, each connected to the mainland banks
A and B, as well as to each other. In total, there were seven bridges connecting these four land

IE T
regions.

The problem was to determine whether it was possible to start from any one of the four land
areas, walk across each of the seven bridges exactly once, and return to the starting point,
without swimming across the river. Despite many attempts by the residents of the city, no such
walk was ever found.

Euler approached this problem by abstracting the physical layout into a mathematical model.
He represented each land area by a vertex and each bridge by an edge, thereby forming a graph.
AJ
Using this graph-theoretic representation, Euler proved that a solution to the Königsberg bridge
problem does not exist. Specifically, the graph corresponding to the bridge system does not
satisfy the necessary conditions for the existence of an Eulerian circuit. This result laid the
foundation for the study of Eulerian paths and Eulerian circuits and established graph theory as
a new and important branch of mathematics.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 6

3.6 Incidence

When a vertex vi is an end vertex of an edge ej , the vertex vi and the edge ej are said to be
incident with each other.
Example:

IE T
In the following figure, edges e2 , e6 , and e7 are incident with vertex v4 .

3.7 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 they are the end vertices of the same edge.
Example 1: Consider the graph shown in the following figure.
AJ
In this graph, vertices v4 and v5 are adjacent. Vertices v1 and v4 are not adjacent. Edges e6
and e7 are adjacent. Edges e3 and e6 are not adjacent.
Example 2: Consider the graph shown in the following figure.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 7

IE T
In this graph, vertices a and f are adjacent. Vertices a and d are not adjacent. Edges {b, c}
and {c, d} are adjacent. Edges {b, c} and {e, f } are not adjacent.

3.8 Degree of a Vertex

The degree of a vertex vi , denoted by d(vi ), is the number of edges incident on vi . A self-loop
is counted twice in determining the degree of a vertex. The degree of a vertex is also referred to
as its valency.

Example: Consider the graph

AJ
Here,

d(v1 ) = d(v3 ) = d(v4 ) = 3,

d(v2 ) = 4, d(v5 ) = 1

3.9 Handshaking Lemma

Let G be a graph with n vertices v1 , v2 , . . . , vn and |E| = e edges. Since each edge con-
tributes two degrees, the sum of the degrees of all vertices in G, is twice the number of edges in

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 8

G. i.e.
n
X
d(vi ) = 2e
i=1

Example: Consider the graph

IE T
In this graph, The sum of the degrees of the vertices is

3.10
d(v1 ) + d(v2 ) + d(v3 ) + d(v4 ) + d(v5 ) = 3 + 4 + 3 + 3 + 1 = 14 = 2|E|,

Corollary (Vertices of Odd Degree)

Theorem: The number of vertices of odd degree in a graph is always even.

Proof: Let G be a graph with vertices

v1 , v2 , . . . , vn .
AJ
From the Handshaking Theorem,
n
X
d(vi ) = 2e
i=1

which is an even number.

Separate the vertices into those having even degrees and those having odd degrees.

The sum of degrees can be written as

n
X X X
d(vi ) = d(vj ) + d(vk ).
i=1 even odd

In the above expression, The left-hand side is even. The first sum on the right-hand side is also
even (being sum of even numbers).

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 9

Therefore, the second sum must also be even:

X
i.e. d(vk ) = an even number.
odd

Since each d(vk ) in this sum is an odd number, the total number of terms in the sum must be

IE T
even.

Hence, the number of vertices of odd degree in a graph is always even.

Problem 1: Determine |V | for graph G = (V, E) if G has 10 edges with two vertices of
degree 4 and others of degree 3.

Solution:
Given: |E| = 10, two vertices have deg = 4, rest have deg = 3
P
By Handshaking lemma: deg(v) = 2|E| = 20 (1)
Let |V | = n.
Then since two vertices of degree 4, remaining n − 2 vertices are of degree 3.

Sum of the degrees of vertices

= 2 × 4 + (n − 2) × 3
X
⇒ deg(v) = 8 + 3n − 6
⇒ 20 = 3n + 2 from (1)
⇒ 20 − 2 = 3n
⇒ 18 = 3n
⇒n=6
AJ
Therefore,G has |V | = 6 vertices.

3.11 Isolated Vertex

A vertex having no incident edge is called an isolated vertex. An isolated vertex has degree
zero.
Example 1: Consider the graph,

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 10

IE T
In this graph, vertex c is the isolated vertex.
Example 2: Consider the graph given below:

In this graph, vertices v4 and v7 are isolated vertices.

3.12 Pendant (End) Vertex

AJ
A vertex of degree one is called a pendant vertex or an end vertex. A pendant vertex is
incident with exactly one edge.
Example 1: Consider the graph,

In this graph, vertices d and f are pendant vertices.

Example 2: Consider the graph,

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 11

IE T
In this graph, vertex v3 is a pendant vertex.

3.13 Edges in Series

Two adjacent edges are said to be in series if their common vertex has degree two.
Example 1: Consider the graph,
AJ
In this graph, the two edges incident on vertex v1 are in series.

3.14 Null Graph

A graph with no edges is called a null graph.

• A null graph may have one or more vertices.

• All vertices in a null graph are isolated vertices.

Example:

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 12

IE T
3.15 Regular Graph

A graph in which all vertices have the same degree is called a regular graph.
A graph in which every vertex has degree r is called an r-regular graph.
Example 1: Consider the graphs given by:

The two graphs shown in the above figure are regular graphs of degree two. They are 2-regular
graphs.
AJ
Example 2: Consider the graph given by:

This is a 3-regular graph.

Example 3: Consider the graph given by:

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 13

IE T
This is also a 3-regular graph.

3.16 Complete Graph

A complete graph is a simple graph in which there exists an edge between every pair of vertices.
Complete graphs of two, three, four, and five vertices are shown in the following figure.

A complete graph is sometimes also referred to as a universal graph or a clique. Since every
vertex is joined with every other vertex by exactly one edge, the degree of every vertex is n − 1
in a complete graph with n vertices.

A complete graph with n vertices is denoted by Kn .

AJ
3.17 Bipartite Graphs

A graph G is called bipartite if its vertex set V can be decomposed into two disjoint subsets
V1 and V2 such that every edge in G joins a vertex in V1 with a vertex in V2 .
We will often draw bipartite graphs with the two parts being top and bottom, or left and right,
as shown here:

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 14

IE T
3.18 Isomorphism

Two graphs G and G′ are said to be isomorphic (to each other) if there is a one-to-one corre-
spondence between their vertices and between their edges such that the incidence relationship
is preserved.
More precisely: Suppose that edge e is incident on vertices v1 and v2 in G; then the corre-
sponding edge e′ in G′ must be incident on the vertices v1′ and v2′ that correspond to v1 and
v2 , respectively.
Another Definition:
Graphs G = (V, E) and G′ = (V ′ , E ′ ) are isomorphic if there exists a bijection f : V →
V ′ such that:
{u, v} ∈ E ⇐⇒ {f (u), f (v)} ∈ E ′
AJ
for all u, v ∈ V .
Notation: We write G ∼ = G′ to denote that G and G′ are isomorphic.
Example 1:
Consider the graphs given below.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 15

T
Vertex Correspondence:

a ↔ v1 b ↔ v2
c ↔ v3 d ↔ v4
e ↔ v5

Edge Correspondence:

Edge 1 ↔ e1 , Edge 2 ↔ e2
Edge 3 ↔ e3 , Edge 4 ↔ e4
J IE Edge 5 ↔ e5 , Edge 6 ↔ e6

There is a one-to-one correspondence between their vertices and between their edges such that
the incidence relationship is preserved. All incidence relationships are preserved. Therefore,
the graphs are isomorphic.
Note:
Except for the labels (i.e., names) of their vertices and edges, isomorphic graphs are the same
graph, perhaps drawn differently.

Example 2: The following figure shows two different ways of drawing the same graph.

Note: It is not always an easy task to determine whether or not two given graphs are isomorphic.

Example 3:
The following figure shows three isomorphic graphs that look different.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 16

3.18.1 Necessary Conditions for Isomorphism

Theorem: Two isomorphic graphs must have:

1. The same number of vertices

IE T
2. The same number of edges

3. An equal number of vertices with a given degree

These conditions are necessary but not sufficient for isomorphism.

i.e.

• If two graphs are isomorphic, they must satisfy all three conditions

• However, satisfying all three conditions does NOT guarantee isomorphism

Example:
The following two graphs that satisfy all three conditions but are not isomorphic:

Both graphs have:

• 6 vertices

• 5 edges
AJ
• Degree sequence: [1, 1, 1, 1, 2, 3]

In the first graph, a vertex of degree 3 is : x and in the second graph a vertex of degree 3 is y. In
the first graph, there are two pendant vertices, u and v, adjacent to x. But in the second graph,
there is only one pendant vertex, w, adjacent to y.

Problem 2: Verify the following graphs are isomorphic or not.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 17

Solution :
Both graphs G1 and G2 contain 6 vertices and 9 edges. However, having the same number of
vertices and edges is not sufficient for two graphs to be isomorphic.

In the graph G1 , there are exactly 2 vertices of degree 2, whereas in the graph G2 there are 3
vertices of degree 2.

IE T
Since graph isomorphism preserves the degrees of vertices, the degree sequences of G1 and G2
are different. Hence, G1 and G2 are not isomorphic.

Problem 3: Verify the following graphs are isomorphic or not.

Solution :
Both graphs G1 and G2 have the same number of vertices and edges; namely, each graph
contains 5 vertices and 6 edges. However, these conditions alone are not sufficient to conclude
that the graphs are isomorphic.
In the graph G1 , there is no pendant vertex (that is, no vertex of degree 1). In contrast, the
AJ
graph G2 contains a pendant vertex.

Since the degree sequences of G1 and G2 are different, the graphs cannot be isomorphic.
Hence, G1 and G2 are not isomorphic.

Problem 4: Check whether the following two graphs are isomorphic.

Solution :
Both graphs G1 and G2 have the same number of vertices and edges; namely, each graph

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 18

contains 8 vertices and 10 edges. However, these conditions alone are not sufficient to conclude
that the graphs are isomorphic.
In G1 , the vertices of degree 2 are not adjacent to each other, whereas in G2 all vertices of
degree 2 are adjacent. Adjacency among degree-2 vertices differs in G1 and G2 ; hence the
graphs are not isomorphic.

IE T
3.19 Walks

A walk in a graph is a finite alternating sequence of vertices and edges, beginning and end-
ing with vertices, such that each edge is incident with the vertices preceding and following it.
Vertices and edges may be repeated in a walk.

A walk is also referred to as an edge train or a chain.

3.19.1 Properties of a Walk

• The set of vertices and edges of a walk in a graph G forms a subgraph of G.

• The vertices with which a walk begins and ends are called its terminal vertices.

• A walk may begin and end at the same vertex.

3.19.2 Open and Closed Walks

• A walk that begins and ends at the same vertex is called a closed walk.
AJ
Example: In the following graph, the red-coloured sequence of vertices a → b →
d → e → a is a Closed walk.

• A walk whose terminal vertices are distinct is called an open walk.

Example: In the following graph, the blue-coloured sequence of vertices e → a →
b → c → d is an open walk.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 19

IE T
3.19.3 Paths

An open walk in which no vertex appears more than once is called a path (or simple path or
elementary path).
Example: Consider the graph :

In the above figure, the sequence of vertices and edges given by v1 a v2 b v3 d v4 is a path,
whereas the sequence v1 a v2 b v3 c v3 d v4 e v2 f v5 is not a path, as the vertex v2 appears
more than once.
AJ
• A path does not intersect itself.

• A self-loop can be included in a walk but not in a path.

3.19.4 Length of a Path

• The number of edges in a path is called the length of the path.

• An edge that is not a self-loop is a path of length one.

3.19.5 Degrees of Vertices in a Path

• The terminal vertices of a path are of degree one.

• All other vertices are called intermediate vertices.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 20

• Intermediate vertices are of degree two.

Note: Degrees are counted only with respect to the edges in the path, not the entire graph.

3.19.6 Circuits

IE T
A closed walk in which no vertex (except the initial and the final vertex) appears more than
once is called a circuit. That is, a circuit is a closed, nonintersecting walk. For example, in the
Graph given above, v2 b v3 d v4 e v2 is a circuit.

• A circuit is a closed, non-intersecting walk.

• Every vertex in a circuit has degree two.

Three different circuits are shown in the following figure.

Other Names for Circuits: A circuit is also known as:

• Cycle

• Elementary cycle
AJ
• Circular path

• Polygon

Note: In electrical engineering, a circuit is sometimes called a loop. Every self-loop is a circuit,
but not every circuit is a self-loop.

3.20 Subgraphs

A graph G1 is said to be a subgraph of a graph G if:

• All the vertices of G1 are vertices of G,

• All the edges of G1 are edges of G,

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 21

• Each edge of G1 has the same end vertices in G1 as in G.

Observations on Subgraphs The following observations can be made:

1. Every graph is its own subgraph.

IE T
2. A subgraph of a subgraph of G is also a subgraph of G.

3. A single vertex in a graph G is a subgraph of G.

4. A single edge in G, together with its end vertices, is a subgraph of G.

Symbolically, we write:

G1 ⊂ G

3.20.1 Edge-Disjoint Subgraphs

Two (or more) subgraphs g1 and g2 of a graph G are said to be edge disjoint if:

E(g1 ) ∩ E(g2 ) = ∅

That is, g1 and g2 do not have any edges in common.

Remarks on Edge-Disjoint Subgraphs:

AJ
• Edge-disjoint subgraphs may have vertices in common.

• They only differ in that no edge is shared between them.

Subgraphs that do not have even vertices in common are called vertex-disjoint subgraphs.

3.20.2 Vertex-Disjoint Subgraphs

• Two subgraphs are vertex disjoint if they have no vertices in common.

• Graphs that have no vertices in common cannot have any edges in common.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 22

3.21 Connected Graphs, Disconnected Graphs, and Compo-

nents

A graph G is said to be connected if there is at least one path between every pair of vertices in
G. Otherwise, G is disconnected.

IE T
Example: Consider the graphs given below.

The first graph in the above figure is connected, but the second graph is disconnected.

It is easy to see that a disconnected graph consists of two or more connected graphs. Each of
these connected subgraphs is called a component. The second graph given above consists of
two components.

Theorem 1:
A graph G is disconnected if and only if its vertex set V can be partitioned into two nonempty,
disjoint subsets V1 and V2 such that there exists no edge in G whose one end vertex is in subset
AJ
V1 and the other in subset V2 .

Proof. Suppose that such a partitioning exists. Consider two arbitrary vertices a and b of G,
such that a ∈ V1 and b ∈ V2 . No path can exist between vertices a and b; otherwise, there
would be at least one edge whose one end vertex would be in V1 and the other in V2 . Hence, if
a partition exists, G is not connected.

Conversely, let G be a disconnected graph. Consider a vertex a in G. Let V1 be the set of all
vertices that are joined by paths to a. Since G is disconnected, V1 does not include all vertices
of G. The remaining vertices will form a (nonempty) set V2 . No vertex in V1 is joined to any
in V2 by an edge. Hence the partition.

Theorem 2:

If a graph (connected or disconnected) has exactly two vertices of odd degree, there must be a
path joining these two vertices.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 23

Proof. Let G be a graph with all even vertices except vertices v1 and v2 , which have odd
degree.

From the Handshaking Lemma, every graph must have an even number of vertices of odd
degree. This property holds for the entire graph G and also for each individual component of
G.

IE T
Since G has exactly two vertices of odd degree, both v1 and v2 must belong to the same
component.

Reason: If v1 and v2 were in different components, then one component would contain exactly
one odd-degree vertex, contradicting Handshaking Lemma.

Since v1 and v2 belong to the same component, there exists a path joining them. (since vertices
in the same component are connected by definition).

Problem 5: Prove that a simple graph with n vertices and k components can have at most
(n − k)(n − k + 1)/2 edges.

Proof:Let G1 , G2 , . . ., Gk , be the k components of a disconnected graph.

Suppose that Gi have ni vertices (ni ≥ 1).

As G has k components and n vertices in total, so we have,

n1 + n2 + · · · + nk = n
k
X
⇒ ni = n · · · (1)
i=1
AJ
k
X
⇒ (ni − 1) = n − k
i=1

Squaring both sides, it follows that

( k )2
X
(ni − 1) = (n − k)2
i=1

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 24

Simplifying the above expression we obtain that

( k )2
X
(ni − 1) = (n − k)2
i=1
Xk X
⇒ (ni − 1)2 + 2 (ni − 1)(nj − 1) = n2 − 2nk + k2
i=1 i̸=j
k
X
⇒ (ni − 1)2 ≤ n2 − 2nk + k2

JIE ⇒

⇒
i=1
X

X
k

i=1
k

i=1
k

i=1
Xk

i=1
(n2i − 2ni + 1) ≤ n2 − 2nk + k2

n2i −2
k
X

i=1
ni +
k
X

i=1

n2i − 2n + k ≤ n2 − 2nk + k2

n2i ≤ n2 − 2nk + k2 + 2n − k
(1) ≤ n2 − 2nk + k2

We know that the maximum number of edges in Gi having ni edges is equal to

ni (ni −1)
2
.
· · · (2)

ni
C2 =

Thus the maximum number of edges of the graph G is

k
1X
maximum number of edges = ni (ni − 1)
2 i=1
k k
1 X 1X
= n2i − ni
2 i=1
2 i=1
k
1 X 1
= n2i − n from (1)
2 i=1
2
1 n
i.e. maximum number of edges ≤ (n2 − 2nk + k2 + 2n − k) − from (2)
2 2

1
= (n2 − 2nk + k2 + n − k)
2
1
(n − k)2 + (n − k)


=
2
(n − k)(n − k + 1)
= .
2
This shows that a simple graph with n vertices and k components can have at most
(n − k)(n − k + 1)/2 number of edges. This completes the proof.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 25

Question Bank

1. Define incidence and degree of a vertex. State and prove the Handshaking Lemma.

2. Define graph and explain the types of graph.

IE T
3. Define the following with suitable examples:

(a) Isolated vertex

(b) Pendant vertex
(c) Null graph

4. Prove that the number of vertices of odd degree in a graph is always even.

5. Explain the Konigsberg bridge problem.

6. Determine |V | for the graph G = (V, E) if G has 10 edges with two vertices of degree
4 and others of degree 3.

7. Explain the following graphs :

(i) Bi-partite graph

(ii) Sub graphs
(iii) Walk
(iv) Path

8. Define the following with an example:

i) Complete graph
AJ
ii) Bipartite graph
iii) Complement graph

9. Define the following with suitable example:

(i) Simple graph

(ii) Complete graph
(iii) Bipartite graph
(v) Isomorphism

10. Define the following with suitable examples:

(i) Simple graph

(ii) Complete graph

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 26

(iii) Bipartite graph

11. Define isomorphic graph and verify the following graphs are isomorphic or not.

IE T
12. Verify the following graphs are isomorphic or not.

13. Show that the following two graphs are isomorphic:

AJ
14. Check whether the following 2 graphs are Isomorphic with each other.

Dr. Shantha Kumari K. AJIET, Mangalore

Lecture Notes - MMC102 Page 27

15. Show that the following graphs are isomorphic

IE T
16. Define Isomorphism in graphs. Check whether the following graphs are isomorphic?

Give reasons for the same.

17. Define a walk, trail, path, circuit and cycle. Give one example for each.

18. Distinguish between walk, path and circuit.

19. Explain paths and circuits in graphs with suitable illustrations.

20. What is a closed walk? Give an example of a closed walk which is not a cycle.

21. Distinguish between edge-disjoint and vertex-disjoint subgraphs.

22. Define connected and disconnected graphs with examples.

23. Prove : “A graph G is disconnected if and only if its vertex set V can be partitioned into
AJ
two nonempty, disjoint subsets V1 and V2 such that there exists no edge in G whose one
end vertex is in subset V1 and the other in subset V2 ”.

24. If a graph (connected or disconnected) has exactly two vertices of odd degree, then prove
that there must be a path joining these two vertices.

25. Prove that a simple graph with n vertices and K components can have at most (n −
k)(n − k + 1)/2 edges.

Dr. Shantha Kumari K. AJIET, Mangalore