G H RAISONI UNIVERSITY, AMRAVATI

Anjangaon Bari Road, Amravati - 444701.

Department of Computer Applications

Discrete Mathematics Notes
MCA Ist SEM Paper Code: BS528T101

UNIT: 4
Syllabus:- Graphs: Finite graphs, incidence and degree, isomorphism, sub graphs and union of
graphs, connectedness, walk, paths, and circuits, Eulerian graphs ,tree properties of trees,
pendant vertices in tree, center of tree, spanning trees and cut vertices, binary tree ,matrix
representation of graph, incidence and adjacency matrix and their properties, applications of
graphs in computer science.

Graph Theory: In discrete mathematics, is the study of the graph. A graph is determined as a
mathematical structure that represents a particular function by connecting a set of points.

The graph is made up of vertices (nodes) that are connected by the edges (lines).

Graph: A graph is a structure amounting to a set of objects in which some pairs of the objects
are in some sense "related". The objects correspond to mathematical abstractions
called vertices (also called nodes or points) and each of the related pairs of vertices is called
an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of
dots or circles for the vertices, joined by lines or curves for the edges.

a graph is denoted as a pair 𝐺(𝑉, 𝐸).

Where V represents the finite set vertices and E represents the finite set edges.
Example: Suppose, a Graph is 𝐺 = (𝑉, 𝐸), where

Vertices, 𝑉 = {𝑎, 𝑏, 𝑐, 𝑑}

Edges, 𝐸 = {{𝑎, 𝑏}, {𝑎, 𝑐}, {𝑏, 𝑐}, {𝑐, 𝑑}}

Diagram:
a b

c
d
 Fig.1

Types of Graph: The graphs are basically of two types, directed and undirected.

Directed Graph: A directed graph is a graph made up of a set of vertices connected by edges, in
which the edges have a direction associated with them.

1 2

Fig.2

Undirected Graph: The undirected graph is defined as a graph where the set of nodes are
connected together, in which all the edges are bidirectional. Sometimes, this type of graph is
known as the undirected network.

1 2

Fig.3
Other types of graphs:

 Null Graph: A graph that does not have edges.

 Simple graph: A graph that is undirected and does not have any loops or multiple edges.
 Multi-graph: A graph with multiple edges between the same set of vertices. It has loops
formed.
 Connected graph: A graph where any two vertices are connected by a path.
 Disconnected graph: A graph where any two vertices or nodes are disconnected by a
path.
 Cycle Graph: A graph that completes a cycle.
 Complete Graph: When each pair of vertices are connected by an edge then such graph
is called a complete graph.

A complete graph with five vertices and ten edges are given below in the figure:
 Fig.4

 Planar graph: When no two edges of a graph intersect and are all the vertices and edges
are drawn in a single plane, then such a graph is called a planar graph
graph.
Finite graph: A finite graph is a graph in which the vertex set and the edge set are finite sets.
Otherwise, it is called an infinite graph
graph.

Incidence: If two edges 𝑒 and 𝑓 have a common vertex A,, the edges are called incident. If the
vertex A is on edge 𝑒,, the vertex A is often said to be incident on 𝑒.

Degrees: Suppose G is a directed graph. The outdegree of a vertex v of G, written outdeg(v), is

the number of edges beginning at v, and the indegree of v, written indeg(v), is the number of
edges ending at v.

Fig.5

Consider the graph pictured in above figure. This is a directed graph. It consists of four vertices,
vertices
𝐴, 𝐵, 𝐶, 𝐷, i.e., 𝑉 (𝐺) = {𝐴, 𝐵, 𝐶𝐶, 𝐷} and the seven following edges: 𝐸(𝐺) = {𝑒 , 𝑒 , . . . , 𝑒 } =
𝐵, 𝐶), (𝐷, 𝐶), (𝐵, 𝐵)} The edges 𝑒 and 𝑒 are said to be parallel
{(𝐴, 𝐷), (𝐵, 𝐴), (𝐵, 𝐴), (𝐷, 𝐵), (𝐵
since they both begin at B and end at A. The edge 𝑒 is a loop since it begins and ends at B.

Example: Consider the graph G in Fig. 5. We have: outdeg (𝐴) = 1, outdeg (𝐵)
( = 4, outdeg
(𝐶) = 0, outdeg (𝐷) = 2,, indeg (𝐴) = 2, indeg (𝐵) = 2, indeg (𝐶) = 2,, indeg (𝐷) = 1
Subgraphs: Let 𝐺 = 𝐺(𝑉 , 𝐸) be a directed graph, and let V ′ be a subset of the set 𝑉 of vertices
of 𝐺. Suppose E ′ is a subset of E such that the endpoints of the edges in E ′ belong to V ′ . Then 𝐻
(V ′ , E ′ ) is a directed graph, and it is called a subgraph of 𝐺.

For example, for graph 𝐺 = 𝐺((𝑉, 𝐸) in Fig. 5, 𝐻 (𝑉 , 𝐸 ) is the subgraph of 𝐺 determine by

the vertex set V where V = {𝐵, 𝐶,
𝐶 𝐷} and
E = {𝑒 , 𝑒 , 𝑒 , 𝑒 } = {(𝐷, 𝐵), ((𝐵, 𝐶), (𝐷, 𝐶), (𝐵, 𝐵)}

Binary operations on Graphs: Binary operations create a new graph from two initial
graphs 𝑮𝟏 = (𝑽𝟏 , 𝑬𝟏 ) and 𝑮𝟐 = (𝑽𝟐 , 𝑬𝟐 ), such as: graph union: 𝑮𝟏 ∪ 𝑮𝟐 and graph
intersection: 𝑮𝟏 ∩ 𝑮𝟐 .

Union of two graphs: The union of two graphs 𝑮𝟏 and 𝑮𝟐 is defined as

𝑮𝟏 ∪ 𝑮𝟐 = (𝑽𝟏 ∪ 𝑽𝟐 , 𝑬𝟏 ∪ 𝑬𝟐 )

Example: (i)

Example: (ii)
Intersection of two graphs: The intersection of two graphs 𝑮𝟏 and 𝑮𝟐 is defined as
𝑮𝟏 ∩ 𝑮𝟐 = (𝑽𝟏 ∩ 𝑽𝟐 , 𝑬𝟏 ∩ 𝑬𝟐 ).

Example:

Path: Path is a sequence of consecutive edges in a graph

graph, i.e., A path is a sequence of edges that
begins at a vertex,, and travels from vertex to vertex along edges of the graph.
graph The number of
edges on the path is called the length of the path.

Example: Consider the following graph:

Then clearly, W → X → 𝑌 → 𝑍 → 𝑋 corresponds to a path of length 4.

Tree: A tree is an undirected graph in which any two vertices are connected by exactly one path
and does not contains any cycle or self
self-loop.

Binary Tree: A binary tree is a tree

tree-like
like structure that is rooted and in which each vertex has at
most two children and each child of a vertex is designated as its left or right child.
Adjacency Matrix: Suppose 𝐺 is a simple directed graph with 𝑚 vertices, and suppose the
vertices of 𝐺 have been ordered and are called 𝑣 , 𝑣 , 𝑣 , ⋯ 𝑣 . Then the adjacency matrix

𝐴 = 𝑎 of 𝐺 is the 𝑚 × 𝑚 matrix defined as follows:

1 if there is an edge 𝑣 , 𝑣  
𝑎 = . Such a matrix A, which contains entries of only 0 or 1,
0 otherwise
is called a bit matrix or a Boolean matrix
matrix.

Note: The adjacency matrix 𝐴 = 𝑎 may be extended to directed graphs with parallel edges
by setting: 𝑎 = the number of edges beginning at 𝑣 and ending at 𝑣 . Then the entries of A will
be nonnegative integers. Conversely, every 𝑚 × 𝑚 matrix 𝐴 with nonnegative integer entries
uniquely
niquely defines a directed graph with 𝑚 vertices.

Example:

1. Find the adjacency matrix 𝑨 of the directed graph given below:

Solution: By using the definition of adjacency matrix of a graph, we obtain the following matrix:
 2.

Solution: Since 𝐴 is a 4 × 4 matrix, 𝐺 has four vertices, 𝑣 , 𝑣 , 𝑣 , 𝑣 . For each entry 𝑎

in 𝐴, draw 𝑎 arcs (directed edges) from vertex 𝑣 to 𝑣 to obtain the following graph:

3. Find the adjacency matrix 𝐴 = 𝑎 of each of the graph given below:

Solution: Set 𝑎 = 𝑛 if there are 𝑛 edges 𝑣 , 𝑣 and 𝑎 = 0 otherwise.

Hence, we get the following graphs:

(Since (𝑎) has no multiple edges and no loops, the entries in 𝐴 are either 0 or 1,, and are 0 on the
diagonal.)