1

UGC NET

DAILY
CLASS NOTES
Computer

Data Structures and Algorithms

Lecture – 6
Graph Theory
 2

Graph Theory
Graph Theory
Content:
1. Basic Terminology of Graph
2. Directed and Un-Directed Graph
3. Singe Graph, Multi Graph and Pseudo Graph
4. Degree of graph
5. Types of Graph
6. Sub Graph & Isomorphic graph
7. Path, circuits, Cycles & connectivity
8. Distance & Diameter
9. Cut Set & Cut Vertices
10. Eulerian Graph
11. Hamiltonian Graph
12. Graph Colouring
13. Chromatic Number

BASIC TERMINOLOGY-
A graph G consists of two sets:
i. a non-empty set V whose elements are called vertices, nodes or points of G.
The group V(G) is called the vertex set of G.
ii. a set E of edges such that every edge e ∈ E associated with ordered or unordered pairs of elements of V. The
set E(G) is called the edge of G.
E(G) = {(u, v) : u, v ∈ V (G)}, E(G) __ V(G) × V (G)
• More formally, a graph G is an algebraic structure (V, E, Ѱ) in which the set V is called the set of vertices,
the set E is the set of edges and Ѱ is a mapping from the set E to the set of unordered or ordered pairs of the
elements of V.
• Mostly, the graph G with vertices V and edges E is written as G = (V, E) or G(V, E), Committing the
function Ѱ.
• 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 u and v are called end points of e. An margin is said o be incident with the vertices it joins.
Thus, the edge e that joins the vertices u and v is said to be incident on each of its end point u and v. any pair
of vertices that is connected by an edge in a graph is called adjacent vertices.
• In graph a vertex is not adjacent to another vertex is called an isolated vertex.
• A graph G(V, E) is said to be finite if it has a finite number of vertices and finite number of Edges;
otherwise, it is a infinite graph. If G is a finite, |V (G)| denotes the number of vertices in G and is called the
order of G and |E (G)| denotes the number of edges in G and is called the size of G. We refer to a graph of
order n and size m an (n, m) graph.
• Although graphs are frequently stored in a computer as list of vertices and edges, they are pictured as
diagrams in the plane in a natural’s way. Vertex group of graph is described as a set of points in a plane and
edge is represented by a line segment or an arc (not necessarily straight). The objects shown in figure.
 3

• It helps when discussing a graph to label each vertex, often with lower case letters as shown above. In figure
1 (a), V = {a, b, c} and E = E{(a, b), (a, c), (b, c)} the member of vertices and edges are |v(G)| = 3 and |E(G)|
= 3 in this graph, the vertices a and b, a and c and b and c are adjacent vertices. Figure 1
• In figure 1(b), V = {u, v, w, x} and E = {(u, v), (v, w), (w, x)}
• Here vertices u and v, v and w, w and x are adjacent, whereas u and w, u and x and v and x are non-adjacent.
The number of vertices and edges are |v(G)| = 4 and |E(G)| = 3.
• The definition of a graph holds no reference to the length or the shape and the positioning of the edge or arc
joining any pair of nodes, nor does it prescribe any ordering of positions of the nodes. Therefore, for a given
graph there is no unique diagram that represents the graph, and it can happen that two diagrams that look
entirely different from one another may represent the same graph. It is to be famed that, in drawing graph, it
is immaterial whether the lines are drawn straight or curved, long or short, what is important is the incident
between edges and vertices are the same in both cases.

UNDIRECTED AND DIRECTED GRAPH-

• An undirected graph G contains set V of vertices and a set E of edges such that each edge e ∈ E is associated
with an unordered pair of vertices.
• Figure 2(a) is an example of an undirected graph we can refer to an edge joining the vertex pair i and j as
either (i, j) or (j, i).
• A directed graph (or digraph) G contains a set V of vertices and a set E of edges such that e ∈ E is associated
with an ordered pair of vertices. In other works, if each edge of the graph G e = (u, v) is represented by an
arrow or directed curve from initial point u of e to the terminal point v. Figure 2(b) is an example of a
directed graph.

Suppose e = (u, v) is a directed edge in a diagram, then

i. u is called the initial vertex of e and v is the terminal vertex of e
ii. e is said to be incident from u and to be incident to v.
iii. u is adjacent to v, and v is adjacent from u.
• Any edge of a digraph by its end-point, the edge is recognize to be directed from the first vertex towards the
second. Graph, both directed and undirected, occur widely in all sorts of problems and before introducing
more terminology we give examples of how graph arise in some familiar contexts.

SIMPLE GRAPH, MULTIGRAPH AND PSEUDOGRAPH-

• An edge of a graph that joins a vertex to itself is called a loop or self-loop i.e., a loop is an edge (v1, v2)
where vi = vj.
• In some directed as well as undirected graph, we may have contained pair of vertices joined by more than
one edges, such edges are called multiple or parallel edges. Two edges (vi, vj) and (vf, vr) are parallel edges
if vi = vf and vf = vr. Note that in case of directed edges, the two possible edges between a pair of vertices
which are opposite in direction are considered distinct. So more than one directed edge in a particular
direction in the case of a directed graph is considered parallel.
 4

• A graph which has neither loops nor multiple edges i.e., where each edge connects two distinct vertices and
no two edges connect the same pair of vertices is called s simple graph. Figure 2(a) and (b) represents simple
undirected and directed graph because the graph do not contain loops and the edges are all distinct.
• Graph which holds multiple edges is called a multigraph. In a multigraph, no loops are allowed.

• In figure 3(a) there are two parallel edges joining nodes v1 and v2 and v2 and v3. In figure 3(b), there are
two parallel edges associated with v2 and v3.
• A graph with self-loops and multiple edges is called pseudograph.

• It famed that there is lack of standardisation of terminology in graph theory. Many words have almost
obvious meaning, which are the same from book to book, but other terms are used differently by different
authors.

DEGREE OF VERTEX-
• It is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that
vertex. The degree of the vertex v in a graph G may be denoted by degG(v).
• In the graph G and H in figure 4 are given below:

In G as shown in figure 4(a)

• degG(x) = 2 = degG(z) = degG(w), degG(y) = 3, degG(r) = 1 and degG(s) = 0 and in H as shown in figure
4(b).
• degH(x) = 5, degH(z) = 3, degH(y) = 5, degH(w) = 4 and degH(r) = 1.
• A vertex of degree 0 is called isolated vertex. A vertex is pendant if and only if it has degree
1. Vertex s in the graph G is isolated and vertex r is pendant. A vertex of a graph is called odd-vertex or even
vertex depending on whether its degree is odd or even.
 5

Degree Sequence of Graph-

In any graph g, we define

• δ(G) = min {deg v: ∈ V(G)} and
• ∆(G) = max {deg v: ∈ V(G)}
• If v1, v2, ..... , vn are the n vertices of G, and let d1, d2, ..... , dn be their degrees.
• If the sequence (d1, d2, ..... , dn) is monotonically increasing i.e. figure 5
• δ(G) = d1 ≤ d2 ≤ ..... ≤ dn = ∆(G).
• Then it is called the degree sequence of graph G.
• For example, the degree sequence of the graph shown in figure 5.
• is (2, 2, 3, 5) as deg (v2) = deg (v4) = 2 deg (v3) = 3 and deg (v1) = 5.

THEORENS-
1. A simple graph with at least two vertices has at least two vertices of same dgree.
2. If G = (V, E) be an undirected graph with e edges. Then

∑ ( )
∈
• i.e., the sum of degrees of the vertices in an undirected graph is even.
• Corollary: In a non-directed graph, the sum of odd degree vertices is even.

IN DEGREE AND OUT DEGREE-

• In a directed graph G, the out degree of a vertex v of G, denoted by outdegG(v) or degg+(v), is the number
of edges beginning from v and the in degree of v, denoted by indegG(v) or degG-(v), is the number of edges
ending at v. The sum of the in degree and out degree of a vertex is called total degree of the vertex. A vertex
with zero in degree is called a source and a vertex with zero out degree is called a sink.
Theorem: If G = (V, E) be a directed graph with e edges, then

∑ ( ) ∑ ( )
∈ ∈
• i.e., the sum of the out degrees of the vertices of a diagraph G equals the sum of in degrees of the vertices
which equal the number of edges in G.

TYPES OF GRAPHS-
• Some important types of graph are introduced here. These graph are often used as example and arise in many
application.

NULL GRAPH-
• A graph which contains only isolated node is called a null graph i.e., the set of edges in a null graph is
empty. Null graph is denoted on n vertices by Nn: N4 is shown in figure 5. Note that every vertex of a null
graph is isolated.
 6

COMPLETE GRAPH-
• A simple graph G is defined to be complete if each vertex in G is connected with every other vertex i.e., if G
contains exactly one edge between each pair of distinct vertices. A complete graph is usually denoted by K n.
It should famed that Kn has exactly [(𝑛−1)]/2 edges. The graph Kn for n = 1, 2, 3, 4, 5, 6 are shown in figure
6.

REGULAR GRAPH-
• A graph in which all vertices are equal degree is called a regular graph. The degree of every vertex is r, and
then the graph is called a regular graph of degree r. Every null graph is regular of degree zero, and that the
complete graph Kn is a regular of degree n – 1. Also, note that if G has n vertices and is regular of degree r,
then G has (1/2) r n edges.

• Note that complete graph need not be regular and a regular graph need not be complete as the following
examples illustrate.

PLATONIC GRAPH-
• Of special interest among the regular graphs are the so-called Platonic graph, the graphs formed by the
vertices and edges of the five regular (Platonic) solids – The tetrahedron, icosahedrons. The graphs are
shown in figure 7.
 7

CYCLE-
• The cycle graph Cn (n ≥ 3), of length n is a connected graph which consists of n vertices v1, v2, .... vn and n
edges {v1, v2}. {v2, v3}, .... {vn-1. Vn}. and {vn, v1}. The cycle C3, C4, C5, and C6 are shown in figure 8.

Cn is a regular graph of degree 2.

WHEELS-
• The wheel graph Wn (n > 3) is obtained from Cn – 1 by adding a vertex v inside Cn-1 and connecting it to every
vertex in Cn-1. The wheels W4, W5, W6 and W7 are display in figure 9.

Wn is a regular graph for n = 4. It has n vertices and 2n – 2 edges.

N-CUBE-
• The N-cube indicated by Qn, is the graph that has vertices representing the 2n bit strings of length n. Two
vertices are adjacent if and only if the bits strings that they represent differ in exactly one bit position. The
graphs Q1, Q2, Q3 are displayed in figure 10. Therefore Qn has 2n vertices and n.2n-1 edges, and is regular of
degree n.

BIPARTITE GRAPH-
• A graph G = (V, E) is bipa tite if the vertex set V can be partitioned into two subsets (disjoint) V 1 and V2
such that every edge in E connects a vertex in V1 and a vertex V2 (so that no edge in G connects either two
vertices in V1 or two vertices in V2). (V-1, V2) is called bipartition of G: Obviously, a bipartite graph can
have no loop as loop connects the same vertex which is not permitted in bipartite graph.
 8

COMPLETE BIPARTITE GRAPH-

• A bipartite graph G = (V, E) is said to be complete bipartite if each vertex of V 1 os connected to each vertex
of V2 where V1 and Vz are the two distinct partition partitions of the vertex set V. Complete bipartite graph
G is denoted by Km,n, where m and n are the number of vertices m vertex sets V 1 and V2. The complete
bipartite graphs K2,3, K2, 4, K3, 3, K3,5 and K2,6 are shown in figure 11. Note that Km,n has m + m vertices and m,
n edges.

NOTE:
1. Any graph K1, n is called a star graph.
2. A complete bipartite graph Km,n is not a regular if m ≠ n.
3. K5 and K3,3 are called Kuratowski graphs.

A PROCEDURE TO CHECK IF GRAPH G IS BIPARTITE OR NOT-

1. Arbitrarily select a vertex from G and include it into set V1.
2. Consider the edges directly connected to that vertex and put the other and vertices of these edges into the set
V2.
3. Pick up one vertex from set V2, and consider the edges directly connected to that vertex, and put the other
end of these edges into the set V1.
4. At each step, check if there is any edge among the vertices of set V1 and set V2.
• If so, the given graph is not bipartite graph, and then return.
• Else continue 2 and 3 alternately until all the vertices are included in the union of sets V1 and V2.
5. If two computed sets are distinct, then the graph is bipartite.
 9

SUBGRAPHAS AND ISOMORPHIC GRAPHS-

SUBGRAPH-
• Some graph applications are concerned with only a part of entire graph. Such a graph is called a sub graph of
the original graph.
• Consider a graph G = (V, E). A graph H = (V’, E’) is called a sub graph of G if the vertices and edges of H
are contained in the vertices and edges o G, that is, if V’ ___ V and E’ ___ E.

So, if H is a sub graph of G, then

i. All the vertices of H are in G.
ii. All the edges of H are in G and
iii. Every edge of H has the same end points in H as in G.
• Some sub graph of a graph G can be obtained by removing certain vertices and edges from G. It is appreciate
that the removal of an edge leaves its points in place, whereas the removal of a vertex necessitates the
removal of any edges with that vertex as an end point.

DIFFERENT TYPES OF SUBGRAPHS-

i. If V’ ___ V and E’ ___ E, then H is called a proper sub graph of G.
ii. A sub graph H of G, is called a spanning sub graph of G if and only if V (H) = V(G).
• i.e., H contains all vertices G but not necessary all edges of G.
iii. A sub graph H (V’ E’) of G (V, E) is called the induced sub graph of G if V’ ___ V and its edge set E’
contains all those edges in G that joins the vertices of set V’ in G.
iv. If a subset U of V and all the edges incident on the elements of U are deleted from a graph G(V, E), then the
resulting sub graph is called a vertex deleted sub graph of G(V, E).
v. If a subset S of E from a graph G(V, E) is deleted, then the resulting sub graph is called an edge deleted sub
graph of G.
• For a given graph G, there can be many sub graphs. Let |V| = m and |E| = n. The total non-empty subsets of
V is 2m-1 and total subsets of E is 2n. Thus, number of sub graph is equal to (2m – 1) × 2n.
• Then number of spanning sub graph is equal to 2n because all vertices are to be included in a spanning sub
graph. For example, in Q3 we have |V| = 8, |E| = 12. Then total number of sub graphs is
• (28 – 1) × 212 = 127 × 4096 = 520192.
• And the total number of spanning sub graph is 212 = 4096.

ISOMORPHIC GRAPH-
• Two graph G1 = (V1, E1) and G2 = (V2, E2) are said to be isomorphic if there exists a functions f : V 1 → V2
such that
i. f is one-to-one onto i.e., f is bijective.
ii. {a, b} is an edge in E1, if and only if {f(a), f(b)} is an edge in E2 for any two elements a, b ∈ V1.
• The condition (ii) says that if vertices a and b are adjacent in G1 then f(a) and f(b) are adjacent in G2. In other
words the function f preserves adjacency relationship and consequently the corresponding vertices in G 1 and
G2 will have the same degree. Any function f with the above properties is called an isomorphism between G 1
and G2.
PATHS, CIRCUITS, CYCLES AND CONNECTIVITY-
♦ In this section we introduce some additional terminology associated with a graph.

WALK-
♦ A walk in a graph G is a finite alternating sequence.
♦ V0 – e1 – v1 – e2 – v2 – e3........... – en – vn
♦ Of vertices and edges of the graph such that each edge ei in the sequence joins vertices vi-1 and vi, 1 ≤ i ≤ n.
The end vertices v0 and vn are the end or terminal vertices of the walk. The vertices v-1, v2, .... , vn – 1 are
 10

called its internal vertices. The integer n, the number of edges in the walk is called the length of the walk. A
walk is called open when the terminal vertices are distinct. For the same end terminal vertices, it is termed as
closed. Note that a walk may repeat both vertices and edges.

SPECIAL TYPE OF WALK-

♦ A walk is called a trial if all its edges are distinct. A trial open or closed depends on whether its end vertices
are distinct or not. A closed trial is called a circuit. A walk is called a path if all its vertices and edges are
distinct. A path in which only repeated vertex is the first vertex is called a cycle to describe such a closed
path.
For example, in the graph given in figure.

i. The sequence v1 – e1 – v2 – e5 – v5 – e8 – v4 – e3 – v4 – e4 – v5 – e5 – v2 – e2 – v3 – e6 – v6 walk of length 8. It

contains repeated vertices v2, v3 and v5 and repeated edge e5.
ii. The sequence v1 – e1 – v2 – e5 – v5 – e8 – v4 – e3 – v4 – e4 – v5 is a trial. It contains repeated vertex v5 but does
not contain repeated edge.
iii. The sequence v1 – e1 – v2 – e5 – v5 – e8 – v4 – e3 – v4 is a path. It does not contain repeated vertex and
repeated edge.
iv. The sequence v2 – e2 – v3 – e3 – v4 – e4 – v5 – e5 – v2 is a cycle. It does not contain repeated vertex and
repeated edge except the first and last vertex.

THEOREMS-
1. If a graph (connected or disconnected) has exactly two vertices of odd degree, there must be a path joining
these two vertices.
2. The minimum number of edges in a connected graph with n vertices is n – 1.
3. The minimum number of edges in a simple graph (not necessary connected) with n vertices is n – k, where k
is the number of connected components of the graph.
4. A simple graph with n vertices and k components cannot have more than [(𝑛−𝑘)(𝑛−𝑘+1)]/2 edges

DISTANCE AND DIAMETER-

♦ In a connected graph G, the distance between the vertices u and v, denoted by d (u, v) is the length of the
shortest path. In figure 13(a), d (a, f) = 2 and in figure 13(b), d (a, e) = 3.
 11

♦ The distance function as defined above has the following properties. If u, v and w are any three vertices of a
connected graph then
1. D (u, v) ≥ 0 and d (u, v) = 0 if u = v
2. D (u, v) = d (v, u) and
3. D (u, v) ≥ d (u, w) + d (w, v)

CUT SET AND CUT VERTICES-

♦ CUT SET: A cut set of a connected graph G is a set of edges whose removal (without removing the end
vertices) from G leaves the G disconnected provided removal of no proper subsets of these edges
disconnects G.

For example, in graph above

i. The edge {e9} is a cut set
ii. The set of edges {e1, e2, e6, e7}
iii. The set of edges {e1, e2, e8, e7} is not a cut set because one of its proper subset {e1, e2, e8} is a cut set.

Thus a cut set S of G satisfy the followings:

1. S is a subset of the edge set E of G.
2. Removal of edge/edges from a connected graph G disconnects the graph
3. No proper subset of G satisfies the condition.
Note: Every edge of a tree is a cut set.

CONNECTIVITY-
♦ To study the measure of connectedness of a graph G we consider the minimum number of vertices and edges
to be removed from the graph in order to disconnect it.
 12

♦ EDGE CONNECTIVITY: Let G be a connected graph. Each cut set of G consists of a certain number of
edges. The number of edges in the smallest cut set (i.e.. cut set containing fewest number of edges) is
defined as the edge connectivity of G and denoted by λ(G). The edge connectivity of the graph in (a) is one
since the removal of edge between c and d results in a disconnected graph.

♦ In (b), the edge connectivity is two since the removal of at least two edges viz (a, b) and (a, c) disconnected
the graph.

Note:
1. The edge connectivity of a tree is one because removal of an edge from the tree disconnects the graph.
2. The edge connectivity of the complete bipartite graph K m,n is a p where p = min (m, n)
3. The edge connectivity of a complete graph of n vertices is n – 1.

THEOREMS-
1. The edge connectivity of a connected graph G cannot exceed the degree of the vertex having the smallest
degree in G.
2. The edge connectivity is less than or equal [2e/n] where [2e/n] represents the integral part of 2e/n.
♦ VERTEX CONNECTIVITY: The vertex connectivity of a connected graph G denoted by k(G) is defined
as the minimum number of vertices whose removal (together with the edges incident on it) from G leaves the
remaining graph disconnected. The vertex connectivity of the graph in figure (a) and (b) are one and two
respectively.

Note:
1. It G is a disconnected graph k(G) = 0
2. The complete graph Kn can not be disconnected by removing any number of vertices, but the removal of n –
1 vertices results in a trivial graph, hence k(Kn) = n – 1.
 13

3. The vertex connectivity of a path is one and then of cycle Cn (n ≥ 4) is two.

♦ SEPARABLE GRAPH: A connected graph G is said to be separable if its vertex connectivity is one.
♦ All other graphs are known as non-separable. The graph shown below is separable.

♦ CUT VERTEX: A cut vertex is a vertex in a separable graph whose removal disconnects the graph. The cut
vertex is also called an articulation point. A given separable graph can have more than one cut vertex. The
graph shown below is separable can have more than one cut vertex. The graph shown below is separable and
both c and e are cut vertices.

THEOREM-
1. A vertex v is a cut vertex of a connected graph if there exist two vertices x and y distinct from v such that
every path between x and y passes through v.
2. The edge connectivity of a graph G cannot exceed the minimum degree of a vertex in G i.e. λ (G) ≤ δ (G).
3. The vertex connectivity of a graph G is always less than or equal to the edge connectivity of G i.e. k (G) ≤ λ
(G)

EULERIAN AND HAMILTONIAN GRAPH-

♦ One of the oldest problem involving graphs is the Konigsberg bridge problems. There were two islands
linked to each other and to the banks of the Pregel River (earlier known as Konigsberg) by seven bridges
shown in figure 14 (a). The problem was to begin at any of the four land areas to walk across each bridge
once and to return the starting point. Euler drew a graph like figure 14(b) for the problem in which a and c
represent the two river banks; b and d the two islands. The arcs joining them represent the seven bridges.
♦ It is clear that the problem of walking each of the seven bridges exactly once and returning to the starting
point is equivalent to finding a circuit in graph (b) that traverses each of the edge exactly once. Euler
discovered a very simple criterion for determining whether such a circuit exists in a graph.

EULERIAN GRAPH-
♦ A circuit in a connected graph is an Euler circuit if it contains every edge of the graph exactly once. A
connected graph with an Euler circuit is called an Euler graph or Eulerian graph.
 14

♦ If there is trial from vertex a to b in G and this trial traverses each edge in G exactly once, then the trial is
called an Euler trail.
♦ In figure 15, d c e a b c represents an Euler trail since it contains all the edges exactly once and vertex c is
represented but start and end vertex are not the same. It is not an Euler circuit as starting and ending at the
same vertex is not possible without repeating an edge cd. Figure 15
♦ The existence of Euler circuit and trial depends on the degree of vertices.
♦ The next theorem provides necessary and sufficient condition for characterising Euler Graph.

THEOREMS-
1. A nonempty connected graph G is Eulerian if and only if its vertices are all of even degree.
2. A connected graph contains an Euler trail, but not an Euler circuit, if and only if it has exactly two vertices
of odd degree.

COROLLARY-
1. A directed multigraph G has an Euler path if and only if it is unilaterally connected and the indegree of each
vertex is equal to its outdegree with the possible exception of two vertices, for which it may be that the
indegree of one is larger than its outdegree and the indegree of the other is one less then its outdegree.
2. A directed multigraph G has n Euler circuit if and only if G is unilaterally connected and the indegree of
every vertex in G is equal to its outdegree.
♦ Thus to determine whether a graph G has an Euler circuit, we note the follow points.
1. List the degree of all vertices in the graph.
2. If any value is zero, the graph is not connected and hence it can not have Euler path or Euler circuit.
3. If all the degrees are ever, then G has both Euler trials but no Euler circuit.
4. If exactly two vertices are old degree, then G has Euler trial but no Euler circuit.

HAMILTONIAN GRAPH-
♦ Hamiltonian graphs are named after Sir William Hamilton, an Irish mathematician who introduced the
problems of finding a circuit in which all vertices of a graph appear exactly once.
♦ A circuit in a graph G that contains each vertex in G exactly once, except for the starting and ending vertex
that appears twice is known as Hamiltonian cycle.
♦ A graph G is called a Hamiltonian cycle if it contains a Hamiltonian cycle.
♦ A Hamiltonian path is a simple path that contains all vertices of G where the end points may be distinct.

THEOREMS
1. (Dirac’s Theorem) A simple connected graph G with n ≥ 3 vertices in Hamiltonian if deg (v) ≥ n/2 for every
vertex v in G.
♦ The graph K5 in figure 16 has Hamiltonian circuit. It has deg (v) = 4 for each v and also have V (G) = 5, so it
satisfies the condition of the theorem.
 15

♦ The graph in figure 16(b) has n = |V (G)| = 5 and has a vertex of degree 2. So it does not satisfy the condition
of the theorem but nevertheless Hamiltonian. The next two theorems provide other sufficient conditions for
graph to be Hamiltonian.
2. A simple connected graph with n vertices and m edges is Hamiltonian if m ≥ [(n – 1) (n – 2)]/2 + 2.
♦ The Hamiltonian graph of figure 16(c) has n = 5, which given [(n – 1) (n – 2)]/2 + 2 = 8 and so it satisfies
the condition and hence the conclusion of the theorem.
3. (Ore’s Theorem) Let G be a single connected graph with n ≥ 3 vertices. If deg (v) + deg(w) ≥ n
♦ For each vertices v and w not connected by an edge i.e. for every pair of non-adjacent vertices of v and w,
then G is Hamiltonian.
♦ For the graph in figure 16 (b), n = 5. There are these pairs of distinct vertices that are not connected by an
edge.
♦ For <v, z> deg (v) + deg (z) = 3 + 3 = 6 ≥ 5
♦ For <w, x> deg (w) + deg (x) = 3 + 2 = 5 ≥ 5
♦ For <x, y> deg (x) + deg (y) = 2 + 3 = 5 ≥ 5
♦ It may be noted that all the theorems started above provide only sufficient criterion. They are not necessary.
♦ A few helpful hints for trying to find a Hamilton cycle in a graph G = (V, E) is the given below:

1. If G has Hamilton cycle, then for all u ∈ V, deg (u) ≥ 2.

2. If a ∈ V and deg (a) = 2, then the two edges incident with vertex a must appear in every Hamilton circuit for
G.
3. If a ∈ V and deg (a) > 2, then as we try to build a Hamilton cycle, once we pass through vertex a, any unused
edges incident with a are deleted from further consideration.
4. A circular graph has both Hamiltonian path and cycle. The complete graph K n (n ≥ 3) is Hamiltonian. The
complete bipartite graph Km,n is Hamiltonian if and only if m = n and n > 1. Qn (n ≥ 2) and Wn(n ≥ 3) has a
Hamiltonian cycle.

GRAPH COLOURING-
♦ Graph colouring is an assignment of colours to elements of a graph subject to certain constraints. The
starting point of graph colouring is the vertex colouring. The other colouring problems like edge colouring
and region colouring can be transformed into vertex colouring. An edge colouring of a graph is just a vertex
colouring of its line graph. The region colouring of a planar graph is the problem of colouring of vertex of its
planar dual graph. In this chapter we present the basic results concerning vertex colouring and edge
colouring of graphs and their applications.

VERTEX COLOURING-
♦ The assign of colours to the vertices of G, one colour to each vertex, so that the adjacent vertices are
assigned different colours is called the proper colouring of G or simply vertex colouring of G. A graph in
which every vertex has been assigned a colour according to a proper colouring is called a properly coloured
graph. The n – colouring of G is a proper colouring of G using n – colours. If G has n colouring, then G is
said to be n – colourable.
♦ CHROMATIC NUMBER: The chromatic number of a graph is the minimum number of colours needed
for a proper colouring i.e. the minimum number of colours needed to assign colours to each vertex of G such
 16

that no two adjacent vertices are of same colour. It is denoted by x (G). Thus a graph G is K chromatic if
x(G) = K.

♦ The graph of figure 1 of n colouring for n = 2, 3, 4 are displayed, with positive integers in small circles
designating the colours. Here x(G) = 2.
♦ In graph colouring, we consider the colouring of simple connected graphs only. This is so because the
colouring of vertices of some component of a disconnected graph has no effect on the colouring of the other
component. Self loops are not considered for colouring. Parallel edges between two vertices can be replaced
by a single edge without affecting the adjacency of vertices.

Note:
i. A graph consisting of only isolated vertices is 1 – chromatic. The chromatic number of a null graph is also 1.
ii. X(G) ≤ n, where n is the number of vertices of G.
iii. A simple connected graph wills one or more edges is at least 2 i.e. x (G) ≥ 2.
iv. Chromatic number of a graph having a triangle is at least 3 (because three colours are required to colours a
triangle)
v. If deg(v) = d for a vertex v in G, then at most d colours are required for proper colouring of the vertices
adjacent to v.
vi. Every k-chromatic graph has at least k vertices, say v1, v2-, ...., vk such that deg (vi) ≥ k – 1, i = 1, 2, ...., k.
vii. If H is a subgraph of G, then x (H) ≤ x(G).

THEOREMS-
1. Every tree with two or more vertices is 2-chromatic.
2. (Chromatic Number of a Bi-Partite Graph (Km,n) The chromatic number of a non-null graph is 2 if and only
if the graph is bipartite.
3. (Chromatic Number of a Complete Graph (Kn) The chromatic number of a complete graph with n vertices
(Kn) is n.
4. (Chromatic Number of cycle (Cn) The chromatic number of a cycle with n vertices (Cn) is
i. 2 if n is even ii. 3 if n is odd
5. A graph G with a least one edge is 2-chromatic if and only if one of the following conditions is satisfied.
a. G is a tree.
b. Every cycle of G has even length
G is a bipartite graph

PW Web/App: [Link]
Library - [Link]