Chapter 5:Graph Theory and Tree

Prepared By:
[Link] Neupane
Associate Professor, Department of
Computer Engineering
KEC,Kalimati
• A graph G = (V, E) consists of two parameters.
i. A set V=V(G), set of vertices or nodes of G.
ii. A set E=E(G), set of edges, joining pairs of distinct vertices of G.
Graph is a pair of two set, vertex set (V) and edge set (E). Where V is non empty
set, and E, subset of V, can be empty also.

Fig: Graph G
Here,
V=V(G)={a,b,c,d}
E=E(G)={(a,c),(a,b),(b,c),(c,d)}
Order and size of a graph:
The order of any graph G is the total number of vertices associated with
[Link] the vertex set of any graph is non-empty,the order of any graph
is at least one. It is denoted by ‘n’.
The size of any graph G is the total number of edges associated with G. It
is denoted by ‘m’
In above graph G, n(G)=4 and m(G)=4
Incident:
An edge is said to be incident to the two vertices if it joins the two
vertices.
Adjacent:
Two vertices are said to be adjacent if they are connected by an edge. Adjacent
vertices are neighbor vertices. In above graph G, vertex a is adjacent to b,c vertices.
Types of graph:
• Labeled graph
A labeled graph is a graph in which labels are assigned to vertex.
• Unlabeled graph
An unlabeled graph is a graph in which vertex have no distinct identification.
• Trivial graph
A graph with exactly one vertex and zero edge is called trivial graph.

• Null graph
If the no. of vertex is finite but no edge between any of its vertices, then it is called
null graph.

• Finite graph
If the no. of vertex and edge is finite then the graph is called finite graph

• Infinite graph
If the no. of vertex and edge is not finite then the graph is called infinite graph
• Undirected Simple graph:
Undirected simple graph is an undirected graph in which there is no loop (edge
from a vertex to itself), and no multiedges (no more than one edge between each
pair of vertices).

• Undirected Multigraph:
Undirected multigraph is an undirected graph with multiedges but not with the loop.
There are multiedges connecting pair of vertices in the following graph, so it is
multigraph.
• Pseudograph
Pseudograph includes loop(s) but may or may not include [Link] is not
directed graph.

• Directed Simple Graph

• Directed multigraph
It is multigraph with direction and loop(s)
Degree of a vertex in an undirected graph:
The degree of a vertex in an undirected graph denoted by deg(v) is a number of
edges incident in the vertex. A loop at a vertex is counted as two edges i.e. incoming
and outgoing while counting degree. A vertex of degree zero is called isolated
vertex and vertex with degree one is called pendant vertex. Loop in a vertex counts
twice to the degree but number of edge of loop is counted one only.

deg (a)= 2
deg (b)= 3
deg (c) = 4
deg (d) = 2
deg (e) = 3
deg (f) = 2
In-degree and Out-degree of a vertex in a directed graph:
In directed graph the in-degree of a vertex v, denoted by deg-(v), is a number of
edges, that have v as their terminal vertex. The out-degree of a vertex v, denoted by
deg+(v), is the number of edges that have v as their initial vertex. Loop at a vertex
adds up both in-degree and out-degree to one more than calculated in-degree and
out-degree.
Find in-degree and out-degree of each vertex.
• Solution:
In-degrees of the vertices are as follows:
deg- (1) = 1, deg-(2) = 3, deg-(3) = 2 and deg- (4) = 1
Out-degrees of the vertices are as follows:
deg+(1) = 1, deg+ (2) = 1, deg+ (3) = 1 and deg+ (4) = 4
The Handshaking Theorem:(Imp)
Let G = (V, E) be an undirected graph with V vertices and E edges, then the sum of
degree of all the vertices of a graph G is twice the number of edges in graph G, that
is 2E = ∑𝑣∈𝑉 deg(𝑣).
Proof:
deg(a) = deg(f)= deg(d)=2
deg(b) = deg(e)=3
deg(c) = 4
We have, LHS = 2*E = 2× 8=16
RHS = ∑𝑣∈𝑉 deg(𝑣) =2+ 2+ 2 + 3 + 3 + 4=16
Therefore, LHS=RHS.
[Link] the handshaking theorem for an undirected graph and use this
theorem to prove the theorem that undirected graph has an even number of
vertices of odd degree(Imp):
Let V1 and V2 be the set of vertices of even and odd degrees respectively in an
undirected graph G = (V, E) .
Then from handshaking theorem we can write,
2E = ∑𝑣∈𝑉 deg(𝑣) = ∑𝑣∈𝑉1 deg(𝑣)+ ∑𝑣∈𝑉2 deg(𝑣)
From above equality, we see that L.H.S is even. In order to hold the above equality
true,R.H.S also should be even. Here, the sum of deg (v) for v ϵ V1 is even since
every vertices has even degree. So for the left hand to be even, sum of deg (v) for v
ϵ V2 must be even. Since all vertices in the set V2 have odd degree the number of
such vertices must be even for the sum to be even. Thus we can say that undirected
graph has an even number of vertices of odd degree.
Example:
Which vertices in following graph are isolated and pendant and what is maximum
degree? What types of graph is it? Determine the number of its edges and sum of
the degrees of all its vertices in given graph.
Solution:
Vertex f is isolated, vertices a, d and j are pendant. Maximum degree is deg (h) = 5.
This graph is pseudograph (undirected loops).
Total number of edges(E)=9
The sum of degree of all the vertices=2*E=2*9=18 [From handshaking theorem]
The Handshaking Theorem for Directed Graph(Imp):
In a directed graph G= (V, E) ,
∑𝑣∈𝑉 deg- (v) = ∑𝑣∈𝑉 deg+ (v) = |E|
Classes of simple graph:(Imp)
Complete graph: The complete graph with n vertices is denoted by Kn. It is the
simple graph that contains exactly one edge between each pair of distinct vertices.
Cycle Graph:
The cycle graph with n vertices is denoted by Cn for n≥[Link] consists of n vertices as
v1, v2,……vn and set of edges as {(v1, v2), (v2, v3), ……(vn-1, vn) and (vn, v1)}.

Wheel Graph:
When a new vertex is added to a cycle Cn and this new vertex is connected to each
of the n vertices in Cn, we obtain a wheel Wn.
 n-cubes(n-dimensional hypercube):
-It is denoted by Qn.
-Number of vertices= 2n.
-Length of bit string=n
-Each vertices is represented by a bit string of length n.
-Two vertices are said to be adjacent if they differ exactly in one bit position.
010 110

01 11 011
111

000 100

00 10
001 101
Operations on graphs:
• Sub graph
A subgraph of a graph G = (V, E) is a graph H = (W, F), where W ⊆ V and F ⊆ E.

• Union
The union of two simple graphs G1 =(V1 , E1) and G2 = (V2 , E2) is the simple graph
with vertex set V=(V1 U V2) and edge set E=(E1 U E2). The union is denoted by G1
U G2
Walk,Trail,Path Circuit and Cycle:(Imp)
Walk:
A walk is a finite alternative sequence of vertices and edges. In walk, vertex can be
repeated and edges can be repeated.
A walk that begins and ends at the same vertex is called a closed walk. If u be
initial vertex, v be terminal vertex. If u = v, then walk w is closed.
A walk that is not closed is an open walk. If u be initial vertex, v be terminal vertex.
If u≠v then it is open walk.
The number of edges encountered in a walk (including multiple occurrence of an
edges) is called the length of the walk.
w: x, y, w, y, v, w is therefore a walk. Length of walk is the no. of edges. Here 5 is
the length.
Trail:
A trail is the walk in which no edge is repeated but vertex can be repeated. Here u,
w, y, x, w, v is a u-v trail even though it repeats the vertex w. But x, y, w, y, v, w is
not a trail as the edge {w,y} is repeated.
Path:
A path is a walk with no vertices and no edge repetition. If no vertex in a walk is
repeated then no edge is repeated either. Hence, every path is a trail. If we traverse a
graph such that we do not repeat a vertex and nor we repeat an edge then it is a path.
u, w, y, v is a u-v path.
Circuit:
A closed trail is a circuit. A circuit in graph G is a closed trail of length 3 or more.
Hence, a circuit begins and ends at the same vertex but repeats no edges. In a
circuit, vertices can be repeated in addition to the first and last. For example:
c : y, w, u, v, w, x, y
c: x, y, w, u, v, w, x
c: w, x, y, w, u, v, w
Cycle: A cycle is closed path. A circuit that repeats no vertex except for the first and
last is a cycle. A K-cycle is a cycle of length K. A 3-cycle is also referred to as a
triangle. A cycle of odd length is called odd cycle, a cycle of even length is called as
even cycle. c' = x, y, v, w, x is a cycle.
Connectedness:Any undirected graph G is said to be connected if there exist a
path between every pair of distinct vertices.
Connected components:
A graph that is not connected is the union of more than one connected graphs that
do not share the common vertex. These disjoint connected sub graphs are called
connected components of a graph.
In the following graph the connected components are: {a, b, c,}, {d, e}, {f, g, h}.
In the following graph G the number of connected components K(G) = 3

Fig:Grpah G
Cut sets:(Imp)
A cut set of a connected graph G is a set S of edges with the following properties
The removal of all the edges in S disconnects G.
The removal of some (but not all) of edges in S does not disconnect G.
A graph G is said to be disconnected if there is no path between any two nodes in a
graph G.
In the figure, set of three edges bd, be and ce is a cut set because we can disconnect
G by removing these three edges, but we cannot disconnect it by removing just one
or two of these edges.
Cut Vertex and Cut Edge:(Imp)
If the removal of a vertex and the edges incident with it in a graph produces more
connected components than in the original graph then such vertex is called a cut
vertex.
A cut edge is an edge by removing which one can partition the graph in to more
connected components.
In the following figure, Cut vertices are c and e and Cut edge is {c, e}
Eulerian (Euler) Graph:(Imp)
Euler Circuit: An Euler circuit is a circuit that uses every edge of a graph exactly
once. An Euler circuit always starts and ends at the same vertex.
Euler Graph: A connected graph G is called an Euler graph, if it has Euler circuit,
that is, if there is a closed trail which includes every edge of the graph G.A
connected graph G is an Euler graph if and only if all vertices of G are of even
degree.
Euler Path: An Euler path is a path that uses every edge of a graph exactly once.
An Euler path starts and ends at different vertices.

C
Necessary and Sufficient Conditions for Euler Circuit and Euler
Path:(Imp)
1)A connected graph G has an Euler circuit if and only if each of its vertices has an
even degree.
2)A connected graph G has an Euler path if and only if exactly two vertices of G
have odd degree.
Q)Which of the following graphs contain a Eularian circuit?
Eulerian for Directed graph:
A non trivial connected digraph D is Eulerian if and only if out degree = in degree
for every vertex.