212CSE2101: Discrete Mathematics Course Material
KALASALINGAM ACADEMY OF RESEARCH AND EDUCATION
DEPARTMENT OF MATHEMATICS
212CSE2101- Discrete Mathematics
Unit 5- GRAPH THEORY
Graph: A graph G = (V, E) consists of a non-empty set V , called the set of
vertices (nodes or points) and set E of ordered or unordered pair of elements
of V , called the set of edges, such that there is a mapping from the set E to
the set of ordered or unordered pairs of element of V .
Note: The number of vertices of a graph is called its order and the number
of edges is called its size.
If an edge e ∈ E is associated with an ordered pair (u, v) or an unordered
pair (u, v), where u, v ∈ V , then e is said to connect or join the nodes u and
v. The edge e is incident to the vertices u and v. The vertices u and v are
called adjacent nodes (or adjacent vertices).
A node which is not adjacent to any other nodes of V is called an isolated
node.
A graph containing only isolated nodes (i.e., no edges) is called a null graph.
In a graph G = (V, E), each edge e ∈ E is associated an ordered pair of
vertices, then G is called a directed graph or digraph. If each edge is associted
with an unordered pair of vertices, then G is called an unordered graph.
Diagrammatic representation of a graph
The vertex set is represented by a set of points in a plane and an edge is
represented by a line segment or an arc joining the two vertices incident with
it. In digraph, the edge e = (u, v) is represented by an arrow or directed
curve drawn from the initial point u to the terminal point v.
v4 v3 v4 v3
t t t t
t t t t
v1 v2 v1 v2
Compiled by: Dr. K. Karuppasamy, www.drkk.in, KARE Page: 1
,212CSE2101: Discrete Mathematics Course Material
Loop: An edge of a graph that joins a vertex to itself is called a loop. The
direction of loop is not significant in digraph.
Multiple/Parallel Edge: In a directed or undirected graph, certain pairs
of vertices are joined by more than one edge, such edges are called multiple
edges or parallel edges. In the case of digraph, the possible edges between
pair of vertices which are opposite in direction are considered distinct.
Simple graph: A graph in which there is only one edge between a pair of
vertices is called a simple graph.
Multi graph: A graph which contains some parallel edges is called a Multi
graph.
Pseudo graph: A graph in which loops and multiple edges are allowed is
called a Pseudo graph.
Degree of a vertex: The degree of a vertex in an undirected graph is the
number of edges incident with it, with the exception that a loop at a vertex
contributes twice to the degree of that vertex. The degree of a vertex v is
denoted by deg(v).
Note 1: The degree of an isolated vertex is zero.
Note 2: If the degree of a vertex is one, it is called a pendant vertex.
Note 3: Minimum degree of a graph is denoted by δ and the maximum
degree of a graph is denoted by ∆.
Degree Sequence: A sequence d1 , d2 , · · · , dn of non-negative integers is
called a degree sequence of a graph of order n if the vertices of G can be
labeled v1 , v2 , · · · , vn so that deg(vi ) = di , 1 ≤ i ≤ n. We write the degree
sequence as a non-increasing sequence.
Example:
Compiled by: Dr. K. Karuppasamy, www.drkk.in, KARE Page: 2
, 212CSE2101: Discrete Mathematics Course Material
v1 v6 v5
r r r
r r r
v2 v3 v4
In the above graph,
deg(v1 ) = 0, deg(v2 ) = 1, deg(v3 ) = 4, deg(v4 ) = 2, deg(v5 ) = 3, deg(v6 ) = 2
Also δ = 0, ∆ = 4 and the degree sequence is : 4, 3, 2, 2, 1, 0
Handshaking Theorem
State and prove Handshaking theorem in Graph Theory.
P
Statement: If G is an undirected graph with e edges then deg(vi ) = 2e.
i
i.e., the sum of the degree of all the vertices of an undirected graph is twice
the number of edges of the graph.
Proof: Since every edge is incident with exactly two vertices, every edge will
contribute 2 to the sum of degree of the vertices.
∴ All the e edges contribute 2e to the sum of the degree of vertices.
P
i.e., deg(vi ) = 2e.
i
Theorem: The number of vertices of odd degree in an undirected graph is
even.
Proof: Let G = (V, E) be an undirected graph. Let V1 and V2 be the sets
of verticesP of G of even and odd degree respectively.
We have deg(vi ) = 2e.
P v i ∈V P
⇒ deg(vi ) + deg(vj ) = 2e · · · · · · (1)
vi ∈V1 vj ∈V2
Since eachP deg(vi ), vi ∈ V1 is even.
We have deg(vi ) = an even number = 2k(say)
vi ∈V1 P
Now (1) becomes, 2k + deg(vj ) = 2e
vj ∈V2
P
⇒ deg(vj ) = 2e − 2k = 2(e − k) = an even number
vj ∈V2
P
Since deg(vj ) is odd, the number of terms contained in deg(vj ) is even.
vj ∈V2
∴ Number of vertices of odd degree is even in an undirected graph.
Compiled by: Dr. K. Karuppasamy, www.drkk.in, KARE Page: 3
KALASALINGAM ACADEMY OF RESEARCH AND EDUCATION
DEPARTMENT OF MATHEMATICS
212CSE2101- Discrete Mathematics
Unit 5- GRAPH THEORY
Graph: A graph G = (V, E) consists of a non-empty set V , called the set of
vertices (nodes or points) and set E of ordered or unordered pair of elements
of V , called the set of edges, such that there is a mapping from the set E to
the set of ordered or unordered pairs of element of V .
Note: The number of vertices of a graph is called its order and the number
of edges is called its size.
If an edge e ∈ E is associated with an ordered pair (u, v) or an unordered
pair (u, v), where u, v ∈ V , then e is said to connect or join the nodes u and
v. The edge e is incident to the vertices u and v. The vertices u and v are
called adjacent nodes (or adjacent vertices).
A node which is not adjacent to any other nodes of V is called an isolated
node.
A graph containing only isolated nodes (i.e., no edges) is called a null graph.
In a graph G = (V, E), each edge e ∈ E is associated an ordered pair of
vertices, then G is called a directed graph or digraph. If each edge is associted
with an unordered pair of vertices, then G is called an unordered graph.
Diagrammatic representation of a graph
The vertex set is represented by a set of points in a plane and an edge is
represented by a line segment or an arc joining the two vertices incident with
it. In digraph, the edge e = (u, v) is represented by an arrow or directed
curve drawn from the initial point u to the terminal point v.
v4 v3 v4 v3
t t t t
t t t t
v1 v2 v1 v2
Compiled by: Dr. K. Karuppasamy, www.drkk.in, KARE Page: 1
,212CSE2101: Discrete Mathematics Course Material
Loop: An edge of a graph that joins a vertex to itself is called a loop. The
direction of loop is not significant in digraph.
Multiple/Parallel Edge: In a directed or undirected graph, certain pairs
of vertices are joined by more than one edge, such edges are called multiple
edges or parallel edges. In the case of digraph, the possible edges between
pair of vertices which are opposite in direction are considered distinct.
Simple graph: A graph in which there is only one edge between a pair of
vertices is called a simple graph.
Multi graph: A graph which contains some parallel edges is called a Multi
graph.
Pseudo graph: A graph in which loops and multiple edges are allowed is
called a Pseudo graph.
Degree of a vertex: The degree of a vertex in an undirected graph is the
number of edges incident with it, with the exception that a loop at a vertex
contributes twice to the degree of that vertex. The degree of a vertex v is
denoted by deg(v).
Note 1: The degree of an isolated vertex is zero.
Note 2: If the degree of a vertex is one, it is called a pendant vertex.
Note 3: Minimum degree of a graph is denoted by δ and the maximum
degree of a graph is denoted by ∆.
Degree Sequence: A sequence d1 , d2 , · · · , dn of non-negative integers is
called a degree sequence of a graph of order n if the vertices of G can be
labeled v1 , v2 , · · · , vn so that deg(vi ) = di , 1 ≤ i ≤ n. We write the degree
sequence as a non-increasing sequence.
Example:
Compiled by: Dr. K. Karuppasamy, www.drkk.in, KARE Page: 2
, 212CSE2101: Discrete Mathematics Course Material
v1 v6 v5
r r r
r r r
v2 v3 v4
In the above graph,
deg(v1 ) = 0, deg(v2 ) = 1, deg(v3 ) = 4, deg(v4 ) = 2, deg(v5 ) = 3, deg(v6 ) = 2
Also δ = 0, ∆ = 4 and the degree sequence is : 4, 3, 2, 2, 1, 0
Handshaking Theorem
State and prove Handshaking theorem in Graph Theory.
P
Statement: If G is an undirected graph with e edges then deg(vi ) = 2e.
i
i.e., the sum of the degree of all the vertices of an undirected graph is twice
the number of edges of the graph.
Proof: Since every edge is incident with exactly two vertices, every edge will
contribute 2 to the sum of degree of the vertices.
∴ All the e edges contribute 2e to the sum of the degree of vertices.
P
i.e., deg(vi ) = 2e.
i
Theorem: The number of vertices of odd degree in an undirected graph is
even.
Proof: Let G = (V, E) be an undirected graph. Let V1 and V2 be the sets
of verticesP of G of even and odd degree respectively.
We have deg(vi ) = 2e.
P v i ∈V P
⇒ deg(vi ) + deg(vj ) = 2e · · · · · · (1)
vi ∈V1 vj ∈V2
Since eachP deg(vi ), vi ∈ V1 is even.
We have deg(vi ) = an even number = 2k(say)
vi ∈V1 P
Now (1) becomes, 2k + deg(vj ) = 2e
vj ∈V2
P
⇒ deg(vj ) = 2e − 2k = 2(e − k) = an even number
vj ∈V2
P
Since deg(vj ) is odd, the number of terms contained in deg(vj ) is even.
vj ∈V2
∴ Number of vertices of odd degree is even in an undirected graph.
Compiled by: Dr. K. Karuppasamy, www.drkk.in, KARE Page: 3
