MODULE 4 GRAPH THEORY IT 123 – Discrete Mathematics
MODULE 4: GRAPH THEORY
Lesson 1: GRAPH AND GRAPH MODELS
Graphs are diagrams or pictorial representation consisting of vertices and
edges that connects these vertices. It is the study of directed and undirected
graphs. A picture of a graph or digraph is a diagram consisting of points or
vertices.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is
the set of edges, connecting the pairs of vertices.
In the above graph,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
The relation of a given element a to another element b is represented with an
arrow connecting a to b.
Graph Terminologies
A. Vertex - a point where multiple lines meet. It is also called a node. Similar to
points, a vertex is also denoted by an alphabet.
Example
The vertex is named with an alphabet ‘a’.
B. Edge = the mathematical term for a line that connects two vertices.
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
Example
‘a’ and ‘b’ are the two vertices and the link between them is called
an edge.
C. Graph (G) is defined as G = (V, E) Where V is a set of all vertices and E is a
set of all edges in the graph.
Example
In this graph, there are four vertices a, b, c, and d, and four edges ab, ac,
ad, and cd.
D. Loop - An edge connecting a vertex to itself
Example 1
In the above graph, V is a vertex for which it has an edge (V, V) forming a
loop.
Example 2
In this graph, there are two loops which are formed at vertex a, and vertex
b.
E. Degree of Vertex
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
1. The degree of a vertex v, represented ±(v), is the number of edges that
contain it (loops are counted twice). A vertex of degree zero (not
connected to any other vertex) is called isolated. A vertex of degree 1
is called pendent.
2. It is the number of vertices adjacent to a vertex V.
Notation − deg(V).
Degree of Vertex in an Undirected Graph
An undirected graph has no directed edges. Consider the following examples.
Example 1
Take a look at the following graph −
In the above Undirected Graph,
• deg(a) = 2, as there are 2 edges meeting at vertex ‘a’.
• deg(b) = 3, as there are 3 edges meeting at vertex ‘b’.
• deg(c) = 1, as there is 1 edge formed at vertex ‘c’
So ‘c’ is a pendent vertex.
• deg(d) = 2, as there are 2 edges meeting at vertex ‘d’.
• deg(e) = 0, as there are 0 edges formed at vertex ‘e’.
So ‘e’ is an isolated vertex.
Example 2
Take a look at the following graph −
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
In the above graph,
deg(a) = 2, deg(b) = 2, deg(c) = 2, deg(d) = 2, and deg(e) = 0.
The vertex ‘e’ is an isolated vertex. The graph does not have any pendent vertex.
Degree of Vertex in a Directed Graph
In a directed graph, each vertex has an indegree and an outdegree.
Indegree of a Graph
• Indegree of vertex V is the number of edges which are coming into the
vertex V.
• Notation − deg−(V).
Outdegree of a Graph
• Outdegree of vertex V is the number of edges which are going out from
the vertex V.
• Notation − deg+(V).
Example 1
Take a look at the following directed graph. Vertex ‘a’ has two edges, ‘ad’ and
‘ab’, which are going outwards. Hence its outdegree is 2. Similarly, there is an
edge ‘ga’, coming towards vertex ‘a’. Hence the indegree of ‘a’ is 1.
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
The indegree and outdegree of other vertices are shown in the following table −
Vertex Indegree Outdegree
a 1 2
b 2 0
c 2 1
d 1 1
e 1 1
F 1 1
g 0 2
Example 2
Take a look at the following directed graph. Vertex ‘a’ has an edge ‘ae’ going
outwards from vertex ‘a’. Hence its outdegree is 1. Similarly, the graph has an
edge ‘ba’ coming towards vertex ‘a’. Hence the indegree of ‘a’ is 1.
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
The indegree and outdegree of other vertices are shown in the following table −
Vertex Indegree Outdegree
a 1 1
b 0 2
c 2 0
d 1 1
e 1 1
F. Adjacency
Here are the norms of adjacency −
• In a graph, two vertices are said to be adjacent, if there is an edge
between the two vertices. Here, the adjacency of vertices is
maintained by the single edge that is connecting those two vertices.
• In a graph, two edges are said to be adjacent, if there is a common
vertex between the two edges. Here, the adjacency of edges is
maintained by the single vertex that is connecting two edges.
Example 1
Which of the vertices and edges are adjacent?
In the above graph −
• a’ and ‘d’ are the adjacent vertices, as there is a common edge ‘ad’
between them.
• ‘c’ and ‘b’ are the adjacent vertices, as there is a common edge ‘cb’
between them.
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
• ‘ad’ and ‘cd’ are the adjacent edges, as there is a common vertex ‘d’
between them.
• ac’ and ‘cd’ are the adjacent edges, as there is a common vertex ‘c’
between them.
G. Parallel Edges
In a graph, if a pair of vertices is connected by more than one edge, then
those edges are called parallel edges.
In the above graph, ‘a’ and ‘b’ are the two vertices which are connected
by two edges ‘ab’ and ‘ab’ between them. So it is called as a parallel
edge.
Example 1
In the above graph, there are five edges ‘ab’, ‘ac’, ‘cd’, ‘cd’, and ‘bd’.
Since ‘c’ and ‘d’ have two parallel edges between them, it a Multigraph.
Example 2
The vertices ‘b’ and ‘c’ have two edges. The vertices ‘e’ and ‘d’ also have
two edges between them. Hence it is a Multigraph.
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
H. Degree Sequence of a Graph
If the degrees of all vertices in a graph are arranged in descending
or ascending order, then the sequence obtained is known as the degree
sequence of the graph.
Example 1
Vertex a b c d e
Connecting to b,c a,d a,d c,b,e d
Degree 2 2 2 3 1
In the above graph, for the vertices {d, a, b, c, e}, the degree sequence is
{3, 2, 2, 2, 1}.
Example 2
Vertex a b c d e f
Connecting to b,e a,c b,d c,e a,d -
Degree 2 2 2 2 2 0
For the vertices {a, b, c, d, e, f}, the degree sequence is {2, 2, 2, 2, 2, 0}.
I. Path A path of length n is a sequence of n + 1 vertices and n consecutive
edges.
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
J. Cycle is a path that begins and ends at the same vertex
K. Weighted graph is a graph whose edges have been labeled with numbers.
The length of a path in a weighted graph is the sum of the weights of the
edges in the path.
Types of Graphs
• Null Graph
A graph with no edges is known as a null graph. The null graph of n vertices is
denoted by
a b
• Simple Graph
When the graph is undirected without any loops or multiple edges, such a graph
is known as Simple/strict graph.
a b
c
• Multi-Graph
When between the same set of vertices, multiple edges are allowed, it is known as
a Multigraph. Multigraph have at least one loop or multiple edges.
a b
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
• Directed and Undirected Graph
When the ordered vertex pair make up the edge set, then the graph G=(V,E) is
known as a directed graph and when the unordered vertex pair make up the
edge set, then the graph is known as a undirected graph.
Undirected Graph. Directed Graph.
• Connected and Disconnected Graph
If any two vertices of a graph are connected by a path, the graph is said
to be connected. If at least two vertices of the graph are not connected
by a path, the graph is said to be disconnected. If a graph G is
disconnected, then every maximal connected subgraph of G is called a
connected component of the graph G.
a b a b
c d c d
A directed graph (digraph) (V, E) consists of nonempty set of vertices V and
a set of directed edges (or arcs) E. Each directed edge is associated with
an ordered pair of vertices. The directed edge associated with the ordered
pair (a, d) is said to start at a and end at d.
• Regular Graph
When all the vertices of the graph have same degree, the graph is said to
be a regular graph. In a graph G of degree r, the degree of each of the
vertex of G is r.
a b
c d
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
• Complete Graph
When exactly one edge joins every two vertices pair, the graph is said to
be a complete graph. The complete graph with n vertices is denoted by
a c
b
• Cycle Graph
The graph with a single cycle is known as a cycle graph. The cycle graph
with n vertices is represented by
a b
c
• Bipartite Graph
When graph G is split into two disjoint sets, V1 and V2, such that each of the
vertex in V1 is joined to each of the vertex in V2 by each of the edge of the
graph. And no edges in G should connect either two vertices in V1 or two
vertices in V2 and such a graph is known as bipartite graph.
• Complete Bipartite Graph
In a bipartite graph, each vertex of the first set is joined to every single vertex
in the second set, such a graph is known as complete Bipartite Graph and
is denoted by
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
• Planar vs. Non-planar graph
Planar graph – Without crossing the edges when a graph can be drawn
plane, the graph is called as a planar graph. It is known as embedding the
graph in the plane.
a b
c d
Non-planar graph – When it is not possible to draw a graph in a plane
without crossing edges, it is non-planar graph.
a b
c d e
Pseudographs - Graphs that may include loops, and possibly multiple edges
connecting the same pair of vertices are sometimes called pseudographs.
Graph Type Edges Multiple edges Loops allowed?
allowed?
Simple graph Undirected No No
Multigraph Undirected Yes No
Pseudograph Undirected Yes Yes
Simple Directed No No
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
Multigraph Directed Yes Yes
Mixed Directed and Undirected Yes Yes
What are Euler Graphs?
If a graph has a closed trail including every edge of the graph G, such a
connected graph is known as Euler graph. The path that is used by every edge
only once is the Euler path which starts and ends at different vertices.
The circuit that uses every edge of the graph only once is known as Euler circuit.
Euler circuit starts and ends at the same vertex. A Euler graph is a connected graph
when all the vertices of G are of even degree.
The above graph is a Euler graph as “a1b2c3d4e5c6f7g” covers all the edges of
the graph.
What are Hamiltonian Graphs?
If there is a cycle in the connected graph that includes every vertex of G is known
as Hamiltonian cycle. The walk that passes through each vertex exactly once in a
graph G is known as Hamiltonian walk.
If G is a simple graph with n vertices, where
for each vertex v, then the graph G is Hamiltonian graph. This is called Dirac's
Theorem.
If G is a simple graph with n vertices, where
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0
MODULE4: GRAPH THEORY IT 123/ IT 51 – Discrete Mathematics
for each pair of non-adjacent vertices x and y, then the graph GG is Hamiltonian
graph. This is called Ore's theorem.
ISUR – ICT – InM – 065 Prepared by: ENGR. MARY JANE C. BANIQUED
Effectivity: October 21, 2018
Revision: 0