MSC-MATS-GRAPH-THEORY-munotes

Page 1

11
GRAPHS
Unit Structure :
1.0 Objectives
1.1 Introduction
1.2 Applications of Graph Theory
1.3 Basic Graph Theory Definitions and Notations
1.4 Different Types of Graph
1.5 Mathematical Representation of Graph
1.6 Isomorphism
1.7 Solved Problem s
1.8 Unit End Exercises
1.0 OBJECTIVES
History and Introduction
Areas of Application
Various Definitions and examples pertaining to graphs
Representation of Graph
1.1 INTRODUCTIO N
The first occurrence of graph in the Mathematical history is
considered to be the classical “Konigsberg Bridge Problem”. The
problem is stated by the great mathematician L. Euler who lived in
Konigsberg, as below:
“Konigsberg is divided into four parts by river Pregel and
connected by seven bridges. Is it possible to t our Konigsberg along a
path that crosses every bridge once and only once and return to the
starting point?”munotes.in

Page 2

2The diagram is given as below.
In proving the fact that the problem is unsolvable, Euler
represented above image in the form of a “graph”, as fol lows.
The points denote the land and the lines denote bridges.
In fact, rather than only proving that above problem is
unsolvable, Euler introduced type of graphs, which can be traceable by
starting from one point, traversing every line once and returni ng to the
starting point, which is termed as Euler Graph. In Chapter 4, we shall
discuss Euler Graphs in detail.
In modern times, Graph theory is applicable in many areas,
such as, Chemistry, Electronics, and Networks, to name a few.
In this chapter, we will get acquainted ourselves with
terminology and basic concepts of Graph Theory.
1.2 APPLICATIO NS OF GRAPH THEORY
Though graph “theory” appears to be a theoretical and hence
pure mathematical term, we shall be amazed to know the areas in
which it can b e applied. In this section, we shall just quote a few in
which graph theory is applied.
1. Graph Theory is helpful in making robots function autonomously.
2. Graph Theory is used to solve actual crimes.
3. Mathematics, often called the universal language, also forms a ridge
between languages. Machine translators use Graph Theory to
achieve good translations efficientlymunotes.in

Page 3

34. Descriptions of cellular activity involve a combination of continuous
models. The analysis of cells requires usage of Graph Theory as
well.
5. Researchers use graph theory to find near -optimal solutions saving
industry time and money. (Travelling salesman’s problem, Chinese
postman’s problem)
6. The Graph Theory is applicable in Road and Rail Traffic network.
7. The Graph Theory is appl icable in planning tournaments (such as
football, chess)
8. Hierarchy in the office, such as Chairperson is the root and people
work under him are at various level.
9. The Graph Theory is present in the virtual world of internet such
www (world wide web, s ocial networking, searching data, data
mining, and so on.
1.3 BASIC GRAPH THEORY DEFI NITIO NSAND
NOTATIO NS
Definition 1.3.1: Simple Graph: Simple graph is a set G (V(G), E(G)),
V(G) the set of vertices (points) and E(G) the set of edges (lines)
disjoint from V(G), together with an incidence function G, that
associates with each edge of G a distinct unordered pair of vertices of
G.
Definition 1.3.2: Directed Graph: A directed graph or digraph is a
graph G (V, E) in which edges are ordered pairs,uv, where,uv V.
That is if there is an edge from utov, there may or may not be an edge
from vtou.
Example 1.3.1:
Fig. 1.3
Example 1.3.2
Fig. 1.4munotes.in

Page 4

4In the example 1.3.1, graph G has,V = u,v,w, x, yand12345678E= e ,e ,e ,e ,e ,e ,e , e.
In the example 1.3.2, graph G has,V = u,v,w, x, yandE = uv,uw,vw, xyNote:
1. Typically number of vertices in a graph G is denoted by letter p
and edges by q.
2. A graph in which both vertex se t and edge set is finite is called as
finite graph.
3. In this and the subsequent chapters, we shall mainly discuss finite
graphs.
4. The graph with no vertices (and hence no edges) is termed as null
graph.
5. A graph with just one vertex is termed as t rivial graph.
6. We are discussing non -trivial and non -null graph.
7. In a graph, if an edge with identical end vertex is called as loop.
8. In a graph, two or more edges with same end vertices are termed
as parallel edges.
9. A graph, in which loop an d / or parallel edges are permitted, is
termed as Multigraph.
10. Graph of Fig. 1.6 is a digraph or directed graph.
In the graph of Fig. 1.2, that is the graph of Konigsberg’s
bridge problem, we can observe parallel edges and the graph of Fig.
1.5, the re is a loop at vertex u.
Fig.1.5 Fig. 1.6
Definition 1.3.3: Degree: The degree of a vertex of a graph is the
number of edges incident to the vertex, with loops counted twice. We
denote degree of vertex v in a graph G is denoted by deg G (v).
In Fig.1.3, degree of u is 3, where as in Fig.1.5, degree of u is 4.
Note: In case of directed graph, every vertex has two types of degrees,
in-degree (that is number of edges entering the ver tex) and out -degree
(that is number of edges leaving the vertex). For the graph of Fig. 1.6,
in-deg (a) = out -deg (a) = 1; in -deg (b) = 1, out -deg (b) = 2; in -deg (c)
= 3, out -deg (c) = 1; in -deg (d) = 1, out -deg (d) = 2; in -deg (e) = out -
deg (e) = 1; inde g (f) = 0, out -deg (f) = 2.munotes.in

Page 5

5Definition 1.3.4: Walk: A walk consists of an alternating sequence of
vertices and edges consecutive elements of which are incident, which
begins and ends with a vertex.
Fig. 1.3,17 7 2ue ve ye ve wis a walk.
Defini tion 1.3.5: Trail: A trail is a walk in which no edges are repeated.
In Fig. 1.3,12 6 5ue ve we ue yis a trail.
Definition 1.3.6: Path: A path is a trail in which no vertices (except
possibly the end vertices) are repeated.
In Fig 1.3,17 8 3ue ve ye we xis a path.
Definition 1.3.7: Circuit: A circuit is a closed trail (that is end vertices
are same) with at least one edge is known as Circuit.
In Fig. 1.3,17 8 3 4 5ue ve ye we xe ye uis a circuit.
It can also be written, only in ter ms of vertices as: uvywxyu .
Definition 1.3.8: Cycle: A cycle is a circuit in which no edge is
repeated.
In Fig. 1.3,12 34 5ue ve we xe ye uis a cycle.
It can also be written as uvwxyu , in terms of vertices alone.
Definition 1.3.9: Subgraph: A gra ph H = (H (V), H(E)) is called as
subgraph of G = (G (V), G(E)), ifHV GVandHE GE.
Fig. 1.6 below is a subgraph of Fig. 1.3.
Fig. 1.6
Let G (V, E) be a graph. We can obtain a subgraph from a
graph in any o ne of the following ways.
1.A subgraph H, can be obtained by deleting vertex subset U of V
and by deleting all the edges from E which are incident with a
vertex in U.munotes.in

Page 6

62.A subgraph H, can be obtained by deleting an edge set D that is
subset of E and ve rtex set of H is same as vertex set of G. Such a
subgraph is called as spanning subgraph of G.
Definition 1.3.10: Connected Graph: Graph G is connected if and only
if there exists a walk between any pair of vertices.
Graph in Fig. 1.3 is connected.
Definition 1.3.11: Disconnected Graph: Graph G is disconnected if and
only if there exists at least one pair of vertices which is not connected
by a walk.
Graph if Fig. 1.4 is disconnected, as there is no walk between vertices
u and x.
The distance d(u, v) between two vertices u and v of a graph G is the
length of the shortest path (often termed as geodesic ) joining them if
any; otherwised u,v =.
In a simple connected graph, distance is a metric; that is for all vertices
u,v, and w,
1.d u,v 0andd u,v 0if and only if u=v .
2.d(u, v) = d(v, u)
3.d u,v + d v,w d u,w
The diameter d (G) of a connected graph G is the length of any
longest geodesic. In the graph of Fig. 1.3, d (G) is 2.
Definition 1.3.12: Complement of a Graph: Let G be a simple graph.
The complementGof G is the simple graph whose vertex set is V (that
is same the vertex set of G) and whose edges are the pairs of
nonadjacent vertices of G.
Fig.1.8 below is the complement of the graph of Fig. 1.3
Fig. 1.8
Definition 1.3.13: Components: Connected component or Component
of a graph is a subgraph in which any two vertices are connected to
each other by paths, and which is connected to no additio nal vertices in
the supergraph.munotes.in

Page 7

7For example graph of Fig. 1.9 below is made up of three components.
Fig. 1.9
Proof: Let G (V, E) be a disconnected and non -trivial graph and GCbe
its complement. Let u,vbe any two vertices in V. If there is no edge uv
in G, then uvwill be an edge in GC. If the edge uvexists in G, then
vertices uandvbelong to same component (say H) of G. As G is
disconnected it has at least two components. Let wbe a vertex in V
which belongs to a component other than H. Then, ther e are no edges
uwandwvin G. Hence, uwandwvbeedges in GC, and hence we get a
u-vpath ( u-w-v)i nGC.
Thus, any between two arbitrary vertices u,vofVthere is a
path in GC.Hence, GCisconnected.
Note: The converse of the above result is not true . That is complement
of a connected graph need not be connected. As an example consider
the graphs in the Fig.1.10 below.
GGC
Fig. 1.10
1.4 DIFFERE NT TYPES OF GRAPH S
Inthis section we shall define and draw different types of
graphs which will be useful for us in further discussion.
Definition 1.4.1: Complete Graph: A graph G is said to be complete, if
every vertex of G is connected to every other vertex in the vertex se t of
G.1.5Mathematical Representation of Graph
Fig. 1.10 (Complete Graph on 6 vertices)munotes.in

Page 8

8Definition 1.4.2: Bipartite Graph: A graph G is said to be bipartite, if
vertex set is divided into two disjoint sets such that no two vertices in
the same set a re connected.
Fig. 1.11 below is an example of a bipartite graph in whichV= V 1 V 2andV1= v0,v1,v2andV2= v3,v4,v5,v6.
Lemma 1.4.1: If G is a bipartite graph having partitions X and Y, thendeg deg
vX v Yvv Proof: We shall prove this lemma by induction on number of edges of
G. LetX= randY= s, for r, s > 1 . (For if r=s=1 , then only one
edge can be drawn and the lemma is trivially true.)
Take subgraph of G consisting of only vertices of G. Now, we shall
start with an induction. Add one edge from any vertex of X and any
vertex from Y. Then,deg deg
vX v Yvv .Now, suppose this is
true for n –1 edges, then on adding one more edge, exac tly 1 is added
tobothdeg
vXvas well asdeg
vYv.
Km,n: If a vertex set of a bipartite graph is partitioned into sets of sizes
m and n, respectively and every vertex in the first set connected to
every vertex in th e set two then such a bipartite graph is known as
complete bipartite graph and is denoted by K m,n.
Pnis as a path on n vertices.
Cnis a cycle on n vertices.
It is very interesting to note the following theorems.
Theorem 1.4.1 Let G be a graph in whic h all vertices have degree at
least two. Then G contains a cycle.
Proof: If G has a loop, it contains a cycle of length one, and if G has
parallel edges, it contains a cycle of length two. So we may assume
that G is simple.
Let01 k - 1kP: =v v ...v vbe a longest path in G. Because the degree of vk
is at least two, it has a neighbour v different from vk−1. If v is not on P,
the path01 k - 1kvv . . . v vvis longer than P, which contradicts that P is a
longest path. Therefore, v=v i, for some i,0≤i≤k−2, andii + 1 kivv ...v vis a cycle in G.munotes.in

Page 9

9Theorem 1.4.2: Let G be undirected graph. G is bipartite if and only if
it has no odd cycles.
Proof: Let G be bipartite graph. Let if possible it has an odd cycle. Let
the cycle be v1v2...v2k+1v1. Let the two disjoint vertex sets of G be A
and B. Then, we have13 4 2vA , vB , vA , vB, and so on
2k+1 1vA , v B, a contradiction that G is bipartite, as1vAaswell as
1vB.
Thus, G has no odd cycle.
Conversely, let G has no odd cycles. We have to show that G is
bipartite.
Without loss of generality, let G be connected, as the same logic can be
applied to each of the components.
Choose any vertex v in the vertex set V of G.
Let A be the set of vertices such that the shortest path from v to each of
the vertex in V is of odd length and B be the set of vertices such that
the shortest path from v to each of the vertex in V is of even length.
Then,vB. AlsoAB Vand AB.
We shall prove that A, B is the partition of G.
For, if not, there exists two incident vertices x1and x 2, both in
A or both in B. Without loss of generality, let both are in A. Then, x1–v
there is a path of odd length, v–x2there is a path of odd length and
hence v–x2–x1–vis in an odd cycle in G, a contradiction.
Theorem 1.4.1 says that an even graph contains a cycle. Now let us
prove even stronger result. That is an even graph can be parti tioned
into cycle and conversely.
Theorem 1.4.3: Let G (V, E) be an even graph. Then the edge set E of
G can be partitioned into cycles such that no two cycles will share an
edge.
Proof: Let G (V,E) be a graph whose vertices are all even. If there is
more than one vertex in G, then each vertex must have degree greater
than 0. Begin at any vertex u. Since the graph is connected (if the
graph is not connected then the argument will be applied to separate
components), there must be an edge {u, u 1}for some v ertex u1≠ u.
Since u1has even degree greater than 0, there is an edge {u1, u2}.
These two edges make a trail from u to u 2. Continue this trail, leaving
each vertex on an edge that was not previously used, until we reach a
vertex v that we have met before. (Note: v may or may not be the same
vertex as u. It does not matter either way.) The edges of the trail
between the two occurrences of v must form a cycle. Call the cycle
formed by this process C 1.I fC 1covers all the edges of G, the proof is
complete. Otherwis e, remove the edges forming C1 from the graph,
leaving graph, say, G 1.All the vertices in G 1are still even. So pickmunotes.in

Page 10

10some vertex u'in G1. Repeat the same process as before, starting with
an edge { u',u'1}. By the same argument, we can generate a new cycle
C2, which has no edges in common with C 1.I fC 2covers all the rest of
the edges of G, then we are done. Otherwise, remove the e dges
forming C 2from the graph, getting graph G 2,which again contains
only even vertices. We continue in this way until we have used up all
the edges of G. By this time we have a number of cycles, C 1,C2,…, C k
which between them contain all the edges of G but no two of them
have an edge in common.
The converse of Theorem 1.4.3 is also true and is obvious. The
readers are encouraged to prove the same.
Definition 1.4.3: Regular Graph: A graph is said to be k–regular, if
degree of every vertex vof G is k.
A complete graph on pvertices is p–1regular. Fig. 1.12 below
gives two examples of 3 –regular graphs.
Fig. 1.12(a) Fig. 1.13(b)
Definition 1.4.4: Tree: A connected graph having no cycle is called
as a tree.
Fig. 1.13 (Tree)
Petersen's Graph : This graph on 10 vertices and 15 edges is very
famous because it tends to be a counter -example to many
generalizations of ideas that work for smaller graphs. As a rule of
thumb, check any c onjecture on the Petersen graph before trying to
prove it.munotes.in

Page 11

11
Fig. 1.14 (Petersen’s Graph)
1.5 MATHEMATICAL REPRESE NTATIO NOF
GRAPH
Even though the pictorial representation of the Graph gives
very good idea of the problem under consideration, to solve th e
problem mathematically as well as electronically, we need to have
mathematical representation of the same.
The best way to represent a graph is using matrices. There are
two types of matrices we shall discuss to represent graph, adjacency
matrix and inc idence matrix.
Definition 1.5.1: Incidence Matrix: Let G (V, E) be a graph having n
vertices and m edges. The incidence matrix of G is annmmatrix;
MG:=( m ve), where m ve= x where xis the number of times vertex v is
incident wi th edge e
The incidence matrix of Fig. 1.3 is
Definition 1.5.2: Adjacency Matrix: Let G (V, E) be a graph having
n vertices. The adjacency matrix of G is annnmatrix; A G:=( m uv),
where
muv=0 if there is no edge from u to v
=1 if there an edge from u to v
=2 ifu=v and there is a loop from u to itself.munotes.in

Page 12

12The adjacency matrix of Fig. 1.3 is
Thus, we observe that in a simple graph, A is symmetric matrix and
sum of the row (/column) elements is degree of the corresponding
vertex.
Now let us prove some results based on the discussion above.
Theorem 1.5.1: The sum of the degrees of the vertices of a graph G is
twice the number of edges. That is:2deg v q, where q is number
of edges in th e graph.
Proof: Consider incidence matrix M of graph G. Sum of entries in
every row is precisely, deg(v), and hence sum of all the entries in M isdegHowever, sum of every column is 2 as every edge has two end
vertices and there a re q columns corresponding to q edges and hence
sum of all the entries in M is 2q. Thus, we get the required result.
Corollary 1.5.1: In any graph, the number of vertices of odd degree is
even.
Proof: The proof is obvious, as if such vertices are odd in n umber thendeg vwill be odd, which contradicts Theorem 1.3.1.
If G (V, E) is a graph having no multiple edges, then it can be
represented using Adjacency list, which specifies the list of adjacent
vertices to every vertex in the grap h. For example, the adjacency list
for the graph of Fig. 1.3 is:uv , w , y ; vu , w , y ; wu , v , x , y ; xw, y and y u,v,w, x    
When a simple graph contains relatively few edges, that is, when it is
sparse, it is usually preferable to use adjacency lists rather than an
adjacency matrix to represent the graph.
Whereas if a simple graph is dense, that is, suppose that it contains
many edges, say, more than half of all possible edges, then using an
adjacency matrix to represent the graph is usually preferable over using
adjacency lists.
Comp utationally speaking, adjacency matrices are more convenient
than adjacency lists.munotes.in

Page 13

131.6 ISOMORPHISM
Let us have a look at the following graphs.
Fig. 1.15 (a) Fig. 1.15 (b)
If the graph in Fig. 1.15(a) is made up of a string, we can changes the
corners appropriately to get the graph of Fig. 1.15(b). The highlighted
and non -highlighted vertices will correspond in these two graphs.
Thus, we can say these graphs are similar though they do not appear to
be the same. This gives us an intuitive idea about isomorphism.
Now, let us define graph isomorphism formally.
Definition 1.6.1: Isomorphism: Two graphs G1 and G2 are isomorphic
(written as12GG), if and only if there exists a one-to-one
correspondence between their vertex sets, which preserves adjacency.
We make following observations from the definition above.
1.There exists a bijection f, from vertex set V 1of G 1to the vertex set
V2of G 2.
2.Number of vertices and edges in both the graphs are same.
3.Ifuvis an edge in G 1then f(u) f(v) is an edge in G 2.
4.For any vertex vin G 1, degree of vin G 1is same as degree of f(v)in
G2.
Once you see that graphs are isomorphic, it is easy to prove it.
However, proving that they are not isomorphic can be sometimes very
complex. It is not practically possible to check all possible
correspondences. Hence, to show that two graphs are non -isomorphic,
we try to find some intrinsic property that differs between the two
graphs in qu estion.
In the following examples we shall check whether given pair of
graphs are isomorphic.
Example 1.6.1:
Fig. 1.16(a) Fig. 1.16(b)
In the figures above, let us have correspondence as:v0 u0,v1 u2,v2 u4,v3 u1andv4 u3. Then, this one to
one correspondence defines isomorphism between these to graphs.munotes.in

Page 14

14Example 1.6.2:
Fig. 1.17(a) Fig. 1.17(b)
In the both the graphs of Fig. 1.17, there are 4 vertices and 4 edges
each. However, in Fig. 1.17(a), 2 vertices are of degree 2 and 2 are of
degree 1 and in Fig. 1.17(b), there are 3 vertices of degree 1 and one is
of degree 3. Thus, these two graphs are not isomorphic.
Example 1.6.3:
Fig. 1.18(a) Fig. 1.18(b)
In the both the graphs of Fig. 1.18, there are 6 vertices and 7 edges
each. However, in Fig. 1.15(a), there is one cycle of length 3 and in
Fig. 1.15(b) has no cycle of length 3.
Thus, these two graphs are not isomorphic.
Example 1.6.4:
Fig. 1.19(a) Fig. 1.19(b)
In the both the graphs of Fig. 1.19, there are 8 vertices and 10
edges each. Also there are 4 vertices of degree 3 and 4 of degree 2 in
each of the graphs. However, in Fig. 1.19 (a) degree of vertices 1 and 3
is 2 and both are connected to vertices 2 and 4 of degree 3 and in Fig.
1.19 (b) vertices 3 and 4 are of deg ree 2 and these are connected to one
vertex of degree 2 and one vertex of degree 3. Hence, we cannot find
one-to-one correspondence between these two graphs and thus they are
not isomorphic.
Definition 1.6.2: Automorphism: An automorphism of a graph is an
isomorphism of a graph to itself.munotes.in

Page 15

15In case of a simple graph, automorphism is just a permutationof its vertex set which preserves adjacency. The automorphisms of a
graph reflect its symmetries. For example, if uandvare two v ertices of
a simple graph, and if there is an automorphism αwhich maps utov,
then uand vare alike in the graph, and are referred to as similar
vertices. Graphs in which all vertices are similar, such as the complete
graph K n, the complete bipartite graph K n,nare called vertex -transitive.
Fig. 1.20
The gr id graphs of Fig. 1.20 have four automorphisms, (1, 2, 3,
4, 5, 6), (2, 1, 4, 3, 6, 5), (5, 6, 3, 4, 1, 2), and (6, 5, 4, 3, 2, 1). These
correspond to the graph itself, the graph flipped leftto -right, the graph
flipped up -down, and the graph flipped left -to-right and up -down,
respectively, illustrated above.
1.7 SOLVED PROBLEMS
1.Let G be a graph which is isomorphic to its complement, then
prove that G must have 4 kor 4k+1 vertices for some k.
Solution:
LetV G = and E G =pq. Since G is is omorphic to its
complement, number of edges in G and GCmust be the same. Also,
total number of edges in G and GCtogether is12pp.H e n c e ,122ppq. Thus,1ppmust be divisible by 4.4pkor41kfor some k.
2.Draw all non -isomorphic graphs on 4 vertices.
Solution: Following figures give 11 non -isomorphic graphs on 4
vertices.
munotes.in

Page 16

163.Which of the following graphs are isomorphic? Which of these are
bipartite? Justify your answer.
G1 G2 G3
Solution: Graph G 1has cycles are of length 4 and no cycle of length 5,
whereas G 3has cycles of length 5 and no cycle of length 4. Hence G 1
and G 3are not isomorphic to each other. Now, we shall show that12GG, by giving following vertex sequence.
Now, if f:12GG,b y f(i) = i for18i. Then, fdefines an
isomorphism from G 1to G 2. Since G 2is isomorphic to G 1, it is not
isomorphic to G 3. We further observe that G 1(and hence G 2) have all
even cycles, so G 1and G 2are bipartite, however, G 3has odd cycles,
hence it i s not bipartite.
4. For each of the following sequences of vertices, state whether or not
it represents a walk, trail, path, closed walk, closed trail, or cycle in the
graph of the figure below.
(i)abcefcbd (ii)abcefcd (iii)abcefcdba (iv)bcefcdb (v)bcdb
(vi)abefcd
Solution: From the definitions of walk, trail and path, we can say the
following:munotes.in

Page 17

17(i) walk (ii) trail (iii) closed walk (iv) closed trail or circuit (v) closed
path or cycle (vi) none
5. Let A be adjacency matrix of a simple graph G, where a ijis relation
between vertices v iand v j. Then (i, j)th term in Akgives number of
walks of lengths kfrom v ito v j.
Hence, prove that “A simple graph G with adjacency matrix A
is bipartite if and only if, for each odd integer r, the diagonal en tries of
the matrix Arare all 0”.
Solution : We use induction on k. When k= 1, aijcounts the edges
(walks of length 1) from vitovj. When k> 1, every vi-vjwalk of length
khas a unique vertex vrreached one step before the end at vj. By the
inducti on hypothesis, the number of vi-vrwalks of length k–1 is entry
(i, r) inAk–1. Thus, the number of vi-vjpaths of length kthatarrive via
vron the last step is (i, j)th term in Ak. Thus, counting the vi-vjwalks
of length kviaAk–1by the defin ition of matrix multiplication, is the
(i,j)th entry in Ak.
By the previous part, (i, i) th entry in Arcounts the closed walks of
length r beginning atvi. If this is always 0, then G has no closed walks
of odd length through any vertex; in particular, G has no odd cycle and
hence is bipartite. Conversely, if G is bipartite, then G has no odd cycle
and hence no closed odd walk, since every closed odd walk contains an
odd cycle.
6. Draw two non isomorphic graphs on 6 vertices such that each has 4
vertice s of degree 3 and 2 vertices of degree 2.
Solution: Graph G 1has triangles however graph G 2has no triangle.
Thus, these two graphs are required non isomorphic graphs.
G1 G2
1.8UNIT END EXERCISES:
1.Prove that a complete graph on p vertices has12ppedges.
2.A graph G has 50 edges, four vertices of degree 2, six of degree 5,
eight of degree 4 and the r est of degree 6. How many vertices does
G have?
3.Prove that the complement of a complement of G is isomorphic to
G.munotes.in

Page 18

184.“If every vertex of G has degree 2 then it contains a cycle”, prove
or disprove.
5.Prove that, every graph has at least two vertice s having same
degree.
6.If G(V, E) is a k –regular bipartite graph having partitions A and
B, then show thatAB.
7.Draw a graph having an adjacency matrix as given below.
8. Which of the following pairs of graphs are isomo rphic? Justify your
answer for every pair.
9.Given nand0rn – 1, where rnis even, define H r,nthe Harary
graph to be an r-regular graph on nvertices, as follows: label the
vertices 0, 1, ··· ,n−1 modulo n, and
Ifriseven, then join each vertex kto12krto12kr
(excluding self).
Ifris odd, then join each vertex ktokto 112krto
112kr, then to12kn.
Draw 4 –regular graph on 7 vertices and 3 regular graph on 8 vertices,
using the definition above.
Will such a graph exist for rnodd? Justify your answer.
munotes.in

Page 19

192
CONNECTIVITY
Unit Structure:
2.0 Objectives
2.1 Cut Vertices, Bridges and Blocks
2.2 Menger’s Theorems:
2.3 Construction of Reliable Communication network:
2.4 Dijkstra’s Algorithm:
2.5 Unit End Exercises
2.0 OBJECTIVES
1.Introduction
2.Vertex -edge connectivity
3.Shortest path -Dijkstra’s algorithm
4.Construction of a reliable network
5.Menger's theorem
In the first chapter, we have defined connected graphs and
component. In this chapter, we shall discuss graph connec tivity in
more details as it is of great importance in the practical applications. In
the computer network, it will be crucial to know whether data can be
transferred if one of the nodes or links fails. Some connected graphs
can be disconnected by removing some vertices or edges. In this
chapter, we shall understand the concept of connectivity further.
2.1 CUT VERTICES, BRIDGES A ND BLOCKS
To understand the importance of connectivity intuitively, let us
have a look at the following graphs of Fig2.1. All th e graphs are on 5
vertices.
G1 G2 G3 G4
Fig. 2.1
G1is a minimal connected graph; deleting any edge disconnects
it. G 2cannot be disconnected by the deletion of a sing le edge, but can
be disconnected by the deletion of one vertex, its cut vertex. There are
no cut edges or cut vertices in G 3, but even so G 3is clearly not as well
connected as G 4, the complete graph on five vertices. Thus, intuitively,
each successive gra ph is better connected than the previous one. Wemunotes.in

Page 20

20now introduce two parameters of a graph, its connectivity and edge
connectivity, which measure the extent to which it is connected.
For any graph G,
:Minimum degree of the graph.
:Maximum degree of the graph.
k: Connectivity of the graph that is minimum number of vertices
that are to be removed to make the graph disconnected or a trivial.
k': Edge connectivity of the graph that is minimum number of
edges t hat are to be removed to make the graph disconnected or a
trivial.
Thus, a connected graph is termed as k -connected, if we need
to remove k vertices to disconnect the graph G.
In the graph G 1of Fig. 2.1,= k = k’ = 1.
In the graph G 2of Fig. 2.1,= 2, k = 1, k’ = 2.
In the graph G 3of Fig. 2.1,= 3, k = 0, k’ = 3.
Students are encouraged to find these parameters for the graph G4 of
Fig. 2.1.
Before we proceed to prove s ome interesting results, let us
define certain terms related to connectivity.
Definition 2.1.1: Cut vertex (Cut point): Let G (V, E) be a connected
graph. VertexvV, is called as cut vertex, if on removing v along
with all its inc ident edges from the graph, resulting graph is
disconnected.
Definition 2.1.2: Bridge: Let G (V, E) be a connected graph. AneEis called as bridge, if on removing e from G, resulting graph is
disconnected.
Definition 2.1.3: Non-separable Graph: A connected, non -trivial graph
having no cut vertices is called as non -separable graph.
Fig. 2.2munotes.in

Page 21

21
Fig. 2.3
The graph of Fig. 2.3 is 2 -connected (i.e. k = 2, e.g., vertices u,
v) and it has k’ = 2 (i.e. on removing edges uy and vx, gr aph is
disconnected)
Definition 2.1.4: Separation: A separation of G of order k is a pair of
subgraphs (H, K) with H ∪K = G and E(H ∩K) = ∅and |V (H) ∩V
(K)| = k. Such a separation is proper if V (H) \V (K) and V (K) \V( H )
are nonempty.
E.g. Sepa ration of graph in Fig. 2.3 is:
Fig. 2.4
Thus, from the definition of a separation, we observe that, a connected
graph has a cut vertex if and only if it has 1 –separation. (i.e.1VH VK= ).
Definition 2.1.4: Block: A block of a grap h is a maximal non -
separable subgraph. If G is non -separable, then G itself is a block.
In the connected graph G having vertex set { v0,v1,v2,v3,v4,v5,
v6,v7,v8,v9} of Fig.2.2, edge v3v5is a bridge. The subgraphs B 1,B2,
B3, and B 4are blocks of t he given graph.
We can observe that end vertices of a bridge are cut -vertices
and an edge is a bridge if and only it is not on any cycle.
From the above discussion we can easily prove following
theorems.
Theorem 2.1.1: Letvbe a vertex of a connected g raph G (V, E). The
following statements are equivalent.
i.vis a cut vertex of G.
ii.There exist vertices uandw, distinct from vsuch that vis on every
u-wpath.munotes.in

Page 22

22iii.There exists a partition of the set of vertices V -{v} into subsets U
and W such th at for any vertexuUandwW, the point vis on
every u-wpath.
Theorem 2.1.2: Letxbe an edge of a connected graph G (V, E). The
following statements are equivalent.
i.xis a bridge of G.
ii.xis not on any cycle of G.
iii.There exist vertices u,vof G such that xin on every path joining u
andv.
iv.There exists a partition of Vinto subsets UandWsuch that for any
pointuUandwW, the edge xin on every path joining uand
w.
Remarks:
If a block B has at least three vertices, then B is 2 -connected.
If an edge is a block of G, then it is a cut -edge of G
Theorem 2.1.3: Two blocks in a graph share at most one vertex.
Proof: Let, if possible, B 1andB2are two blocks of G, sharing two or
more vertices. Then the deletion of any one of the vertices will not
disconnect B 1or B 2. Thus, B1B2 is a subgraph of G having no cut
vertex and a block of G, which contradicts maximality o fB1and B 2.
Blocks of G partition its edge set.
If two blocks share a vertex, then it must be a cut -vertex of G.
Definition 2.1.5: Block Graph: Block graph of a graph G is a bipartite
graph H in which one partition set consists of cut vertices of G and the
other has a vertex bifor every block Biof G. We include ( v,bi)a sa n
edge if cut vertex vis in block Bi.
Let us illustrate the definition with the help of following graph.
Fig. 2.4munotes.in

Page 23

23The graph of above Fig.2.4 has four blocks B1,B2,B3,B4and
three cut vertices v1,v2,v3. Hence, Block graph of the same is as
below:
Fig. 2.5
Theorem 2.1.4: The block graph of a connected graph is a tree.
Proof: We have seen that a block graph of a connected graph is a
bipartite graph. Let B(G) be a block gra ph of a connected graph G. By
adding edges in a block of G, we do not change B(G), so let us assume
that blocks are complete graphs. Since G is connected, B(G) is also
connected. Now, we shall show that B(G) has no cycle.
Let if possible, it has a cycle C such that its alternate vertices
correspond to cut vertices and blocks of G. It can be shown in the
diagram of Fig. 2.6 below. White points represent vertices with respect
to blocks and black points represent vertices with respect to cut
vertices.
Fig.2.6
Let cut vertices of G in order along C be v0,v1,v2, ....,v k,v0,then
v0v1v2...vkv0is a cycle CG. If BC, then BC is a subgraph of
G consisting of complete graph B together with a cycle C in which one
edge is in B and atleast one edge not in B. Therefore, BC has no
cutvertex, which contradicts maximality of B.
Now, we shall prove the relationship among k, k’ and.
Theorem 2.1.5: For any graph G, kk’.
Proof: We shall prove second part of the inequality first. If G has not
edges, then k’ = 0. Otherwise, if every edge incident to a vertex ofmunotes.in

Page 24

24minimum degree is removed, the resulting graph is disconnected. In
both these extreme cases, k’.
Now we shall prove kk’. Here we need to consider many
cases. If G is disconnected or trivial, k = k’ = 0. If G is c onnected and
has a bridge at edge e, then k = 1, because either G has a cut -vertex
which is an end vertex of e or G is K 2. Finally, let G has edge -
connectivity k’, such that k’2. Then, removal of k’ –1 of these
edges will produ ce a bridge, say, e =uv. For each of these k’ –1 edges,
select an incident vertex different from u or v. Removal of these k’ –1
vertices also removes these k’ –1 edges and possibly more. If the
resulting graph is disconnected then k < k’. If not, e = uv is s till a
bridge in this resulting graph and removal of u or v will result into
either trivial or disconnected graph, giving kk’.
Following graph in Fig. 2.3 has k = 2, k’ = 3 and= 4.
Fig. 2.6
2.2MENGER’S THEOREMS
Menger’s theorem gives characterisation of connectivity of
finite, connected graphs. If uandvare any two vertices in a connected
graph, then two paths connecting uandvare said to be disjoint or
vertex disjoint, if they have no vert ex (and hence no edge) in common.
The paths are said to be edge disjoint, if there is no edge common.
Menger discusses minimum number of disjoint paths between
any pair of vertices. Menger proved the results for vertex -connectivity
as well as edge -connect ivity.
Before we discuss Menger’s theorem, let us have a look at the
graph of Fig. 2.7 below:
Fig. 2.7munotes.in

Page 25

25In the Fig. 2.7, we observe that there are three vertices disjoint
from u to v, viz. u -x-y-t-v, u-zvandu-r-s-v.
Vertex version of Menger’s theore m discusses about the vertex
disjoint path.
Theorem 2.2.1 (Menger’s Theorem –Vertex Form): The minimum
number of vertices separating two non -adjacent vertices s and t is the
maximum number of number of disjoint paths connecting s and t.
Proof: Ifkvertices separate sandt, then obviously there can be no
more than kdisjoint paths. We shall show that these are exactly k. That
is if there are kvertices separate sand tthen exactly kinternally
disjoint paths separate sandt. This is true if k=1. So letk> 1 and if
possible the result is wrong. That is it takes less that k disjoint paths to
disconnect sandt.L e t hbe the smallest such k, and let Fbe a graph
with the minimum number of vertices for which the theorem fails for
h. We remove edges from Funtil we obtain a graph G such that h
vertices are required to separate sandtin G but for any edge xof G,
only h–1 vertices are required to separate sandtin G –x. We first
investigate the properties of this graph G, and then complete the proof
of the theorem.
By the definition of G, for any edge xof G, there exist a set
S(x) of h–1vertices which separates sandtin G –x. Now G –S(x)
contains at least one s-tpath, since it takes hpoints to separate sandt
in G. Each such s-tpath must contain the edge x=uv, since it is not a
path in G –x.S ou, vS(x) and if us, t, then S( x){u} separates
sandtin G. If there is a point wadjacent to both sandtinG ,t h e nG –
wrequires ( h–1) points to separate sandtand so it has h–1 disjoint
s-tpaths. Replacing w, we have hdisjoint s-tpaths in G. So we have
shown:
(I) No point is adjacent to both sandtin G.
Let W be any collection of hpoints separa tingsandtin G. An
s–W path is a path joining s with some wiW and containing no
other point of W, call the collections of all s-W paths and W -tpaths Ps
andPt, respectively.
Then each s-tpath begins with a member of Psand ends with a
member of Ptbecause every such path contains a point of W.
Moreover, the paths in PsandPt, have the points of W and no others in
common, since it is clear that each wiis in at least one path in each
collection and, if some other point we re in both an s-W and a W -tpath,
then there would be an s-tpath containing no point of W. Finally,
either Ps–W={ s} orPt–W={ t}, since, if not, then both Psplus the
lines { w1t, w 2t, ...} and Pt plus the lines { sw1, sw 2, ...} are graphs with
fewer points than G in which sand tare nonadjacent and h-
connected, and therefore in each there are hdisjoint s-tpaths.
Combining the s-W and W -tportions of these paths, we can construct
hdisjoint s-tpaths in G, and thus have a contradiction. Therefore we
have proved:munotes.in

Page 26

26(II) Any collection W of hpoints separating sandtis adjacent either to
sor to t.
Now we can complete the proof of the theorem. Let P =
{s,u1,u2,...t} be a shortest s-tpath in G and let u1u2=x. Note that by (I),
u2t. Form S(x)={ v1,v2, ..., v k–1} as above, separating sandtin G –
x.B y( I ) , u1tG and hence by II with W=S ( x ){u1},sviG, for
alli. Thus, by (I), vitG, for every i. However, if we pick W = S(x){u2} instead, we have by (II) that su2G, contradicting our choice
ofPas a shortest s-tpath, and completing the proof of th e theorem.
Definition 2.2.1: Line Graph: Let G be any graph. Line graph of G,
denoted by L (G) is such that each vertex in L(G) represents an edge in
G and if two edges are adjacent in G then there is an edge between two
vertices of L(G) corresponding to these two edges.
Fig. 2.8 below gives an example of a graph and its line graph.
Fig. 2.8
Theorem 2.2.2 (Menger’s Theorem –Edge Form): A graph G is k -
edge-connected if and only if it contains k edge -disjoint paths between
any two vertices.
Proof: App ly Menger’s theorem -vertex form on the line graph of G.
2.3 CO NSTRUCTIO NOF RELIABLE COMMU NICATIO N
NETWORK
As we have seen in the first chapter, one of the applications of
graph theory is to represent graph as a communication network. While
constructing this network, it is necessary to make it sure that it does not
get disconnected too often. Higher the connectivity and the edge
connectivity of the network, the more reliable the network is.
Minimum cost spanning tree constructed using Kruskal’s algorithm
(discussed in chapter 3), has connectivity 1 and hence it is not much
reliable. Therefore, we try to generalise the problem.
Letkbe given integer and let G be a weighted graph. Our aim
is to find minnimum weight k–connected spanning subgraph. If k=1 ,
the problem can be solved using Kruskal’s method. Fork> 1, the
problem is difficult and no solution is known. However, if G is a
complete graph having unit weight, then it can be solved by the
method given below.
If G is a complete graph on n vertices having unit weight, then
the problem is simply to find a minimum m–connected ( mspanning subgraph, with as few edges as possible. We shall denote by
f(m, n) , the least number of edges an m–connected graph on nverticesmunotes.in

Page 27

27canhave and denote such a gra ph by Hm,n. Structure of Hm,ndepends
on parities of mandn, and we have three cases as below.
Case 1: Let m be even, m=2r . Number the vertices of graph on n
vertices from 0 to n–1.
Connect vertices iandjifj–is(mod n) is such that 0sr.
Case 2: Let mbe odd, m = 2r + 1 andneven. First draw Hm,nand
then add edges from itoi+(n/2).
Case 3: Let mbe odd, m = 2r + 1 and n is also odd. Then H2r+1,nis
constructed first by drawing H 2r,nand then by adding edges joining
vertex 0 to vertices12nand12nandvertex ito vertex12nifor112ni.
These three cases are sho wn in the Fig. 2.9(a), (b) and (c) below.
(a) (b) (c)
Fig. 2.9
2.4 DIJKSTRA’S ALGORITHM
If G (V, E) is any connected graph and u,vare any two
arbitrary vertices in V. Then , there may exist multiple paths from uto
v. One of the very important and practical applications of Graph theory
is to find the shortest path from one vertex (node) to the other. The
term “shortest” may refer to minimum distance, least cost or least time .
One of the most important algorithms which is of prime
importance in Graph Theory is credited to a computer scientist
Dijkstra. Main reason for the popularity of Dijkstra’s algorithm is that
it provides exact optimal solution to a large class of shorte st path
problems, and it is important theoretically, practically as well as
educationally.
Before we proceed to discuss the example and algorithm, let us
have a look at its salient features.
Algorithm gives solution to single source shortest path problem s.
It works on both directed and undirected graphs.
All edges must have non -negative weights.
Graph must be connected.munotes.in

Page 28

28Before we proceed to the algorithm, let us understand the same
with the help of an example.
Fig. 2.7
Let us say, we have to find mini mum distance from v0to every
other vertex and the shortest path from v0to every other vertex.
We shall start with vertex v0and subsequently visit every
vertex and once all the vertices are visited, we will terminate the
procedure.
Let us introduce som e parameters for the same.
L(i) : Shortest distance between v0and vertex i.
V : Set of visited vertices
U : Set of vertices not visited so far
w(i, j): Weight of edge connecting vertices iandj
P(i) : Shortest path from v0toi.
To begin with, we shall have L(v0)=0 andL(v1)=L(v2)=
L(v3)=L(v4)=L(v5)=.V= , U={v0,v1,v2,v3,v4,v5},P(v1)=
P(v2)=P(v3)=P(v0)=P(v5)=.
Initially, let v0be only visited vertex and hence V = { v0}. We check all
the edges having one end point in V an d other in U for their distances
and update V by picking up vkfor which L(vk) is minimum. We keep
on updating paths from v0tovkevery time. We shall continue the
process till all the vertices of the graph are visited.
Step I:
V={ v0}, P( v0)={ v0}. Now observe all the vertices adjacent to v0
and update these parameters as below:
L(v1)=m i n {L(v1), L(v0)+w ( v0,v1)} = min{, 0 + 2} = 2, P( v1)=
{v0,v1}
L(v2)=m i n {L(v2), L(v0)+w ( v0,v2)} = min{, 0 + 3} = 3, P( v2)=
{v0, v2}
As L( v1) is minimum, V = { v0,v1}.
Step II:
L(v2)=m i n {L(v2), L(v1)+w(v1,v2)} = min {3, 2 + 6} = 3, P( v2)=
{v0,v2}munotes.in

Page 29

29L(v3)=m i n {L(v3), L(v1)+w(v1,v3)} = min {, 2 + 5} = 7, P( v3)=
{v0,v1,v3}
L(v4) = min {L(v4), L(v1) +w(v1,v4)} = min {, 2 + 3} = 5, P( v4)=
{v0,v1,v4}
As L (v2) is minimum, V = { v0,v1,v2}
Step III:
L(v3)=m i n {L(v3), L(v2)+w(v2,v3)} = min {7, 3+ } = 7, P(v3)={v0,
v1,v3}
L(v4) = min {L(v4), L(v2)+w(v2,v4)} = min {5, 3+1} = 4, P(v4)={v0,
v2,v4}
As L( v4) is minimum, V = { v0,v1,v2,v4}
Step IV:
L(v3)=m i n{ L ( v3), L(v4)+w(v4,v3)} = min{7, 4+1} = 5, P( v3)={ v0,
v2,v4,v3}
L(v5) = min{L( v5), L(v4)+w( v4,v5)} = min { , 4+4} = 8, P(v5)=
{v0,v2,v4,v5}
As L ( v3) is minimum, V = {v 0,v1,v2,v4,v3}
Step V:
L(v5)=m i n {L(v5), L(v3)+w(v3,v5)} = min {8, 5+2} = 7, P( v5)={v0,
v2,v4,v3,v5}
Thus, V={v0,v1,v2,v3,v4,v5}.
All the vertices are visited and we have found the shortest path
and distance from v0to every other vertex.
In fact, what we have presented above is Dijkstra’s shortest
path method.
Now, let us present the steps of the algorithm.
Dijkstra’ s Shortest Path Algorithm:
Let G (V, E) be any connected, weighted graph, with G V={v0,
v1,v2, ..., v n}.
Parameters:
L(vi) : Shortest distance between source s=v0and vertex vi.
P(vi) : Set of vertices giving shortest path from stovi.
V : Set of vis ited vertices
U : Set of vertices not visited so far
w(vi,vj) : weight of an edge from vitovj.
z : Destination vertex
Initial Values:
V=,U=G V ,L ( s=v0) = 0, P(s=v0)={v0}
L(vi)=; for 1in
P(vi)=; for 1inmunotes.in

Page 30

30Procedure:
While zU
Begin
u : vertex in U with L( u) minimum
V: = V{u}
For every xU
Begin
If(L(x) > L(u) + w (u, x)) then
(x) := L(u) + w(u, x)
P(x) := P(u){x}
End If
End
End
Solved Problems:
1. If G is a bipartite k -regular graph such that k2, then prove that G
has no bridge.
Solution: We will prove the result by contradiction. Assume G has a
bridge e=u v .
Let’s start with a couple of easy observations. Firstly, note that
a bridge affects only the connected component it belongs to. Every
connected component of a bipartite kregular graph is itself bipartite k-
regular, so we can assume, without loss of generality, that G is a
connected bipartite k-regular graph. Secondly, removal of an edge can
split a connected graph into at most two connected components -to see
why, observe that if we restore the edge, the graph should be
connected, but three or more disjoint components cannot be linked by a
single edge. Now assume G has classes A and B, where u∈A and v
∈B. Removal of esplits G into disjoint components G 1and G 2.L e t
A0be the set of vertices of A in G 1and A 00be those in G 2-both these
sets are non -empty. Similarly let B 0,B00be the vertices of B in G 1and
G2respectively. Observe that t he bridge emust be the only edge
linking G 1and G 2, and assume without loss of generality that u∈A0
andv∈B00. Now look at G 1, which is a bipartite graph with classes
A0and B 0. Since eis the only edge linking G 1and G 2, every other edge
of G inciden t on A 0or B 0is retained in G 1.S oe v e r yv e r t e xi nA 0and
B0still has degree kin G 1, except uwhich has degree k−1. Let a :=
|A0| and b := |B 0|. Since no edge links two vertices in B 0(bipartite
property), the number of edges in G 1is simply kb (eve ry edge is
incident to some vertex in B 0, so we can add up the degrees of the
vertices in B 0). Similarly, adding up the degrees in A 0instead, the
number of edges is k(a−1) + k−1. Equating the two formulae, we
have k(a−1) + k−1=kb,⇒k(a−b)=1 . But this implies k= 1,
which contradicts the given condition that k≥2. Hence the bridge
cannot exist.
2. If G is a graph on pvertices such that12p, then prove that G is
connected.munotes.in

Page 31

31Solution: Let, if possible, G is not connec ted and has at two
components G 1and G 2(same argument can be used, for more than two
components). Let |V(G 1)| = r and |V(G 2)| = s, such that rs. Then,111122 2pp pr  .A contradiction to given
hypothesis that12p.
3. If G is k’ edge -connected having q edges and p vertices, then2kpq.
Solution :From Theorem 2.1.5, we have k’i.e. pk’pAsminimum degree of G is, we havedeg 2pv q .( B y
Theorem 1.5.1)
Thus,2kpq.
2.5UNIT END EXERCISES:
1. Find cut vertices and cut edges of the following graphs.
G1 G2 G3
2. Find vertex connectivity (k) and edge connectivity (k’) for the
following graphs.
3. Give an example of a graph for which k < k’ <.
4. Find blocks of the following graph and hence draw its block graph.
5. Use Dijkstra’s algorithm to find the shortest path from s to t in the
following graph.munotes.in

Page 32

32
6. If G is a connected graph having a bridge, then show that G has a cut
vertex. Is the conve rse true? Justify your answer.

munotes.in

Page 33

333
TREES
Unit Structure:
3.0 Objectives
3.1 Introduction
3.2 Characterisation of Trees
3.3 Edge Cuts and Bonds
3.4 Graphs and Vector Space
3.5 Cayley’s Formula
3.6 Minimal Cost Spanning Tree and Kruskal’s Algorith m
3.7 Rooted and Binary trees
3.7.1Breadth First Search
3.7.2Depth -First Search
3.8 Huffman Codes
3.9 Unit End Exercises
3.0 OBJECTIVES
1.Characterization of trees.
2.Detailed discussion on spanning trees.
3.Kruskal’s algorithm
4.Huffman Code
5.To know edge cuts, bonds, cut vertex and cut edge.
6.Construction of vector space and cycle subspace associated with a
graph
7.Graph traversals
3.1 INTRODUCTIO N
In the chapter 2, we have defined trees and also its relationship
with block graphs. In this chapter, we shall explore trees in details and
also discuss a few practical applications of the same.
First, we will be enumerating all the trees on n vertices. Before
that, let us draw trees on 7 vertices. A Few of such trees are shown in
Fig. 3.1.munotes.in

Page 34

34Following figu re gives trees on 7 vertices.
Let us know a few more terms related to tree. As tree is an
acyclic graph, acyclic graphs are called as Forest.
We have seen a spanning subgraph of a graph G in the chapter
1. If a spanning subgraph of a connected graph i sat r e e ,i ti sc a l l e da s
spanning tree. Spanning trees are of utmost importance in the
applications of graph theory.
Fig. 3.2(b) below is a spanning tree of the graph of Fig.3.2(a).
We also observe the following facts about trees from the
definition of tree and the discussion so far.
1.In a tree, any two vertices are connected by exactly one path. (For
more than one path would result into a cycle.)
2.From Theorem 1.4.1, we know that if degree of every vertex is at
least two, then the graph contai ns a cycle. And hence every tree has
at least one vertex of degree at most one. In fact, if the tree is non -
trivial then it has a vertex of degree exactly one. Vertex of degree
one in a tree is termed as leaf.
3.Result: For a tree p = q + 1, or number of vertices is exactly one
more than the number of edges.
Proof: Let T be a tree having p vertices and q edges. If T is trivial,
then p = 1 and q = 0. Hence, the result is true. If T is K2, then p = 2
and q = 1. Again the result holds true. Let T be non -trivial and not K2.
We shall prove the result by induction on number of vertices. Let the
result be true for a tree having less than p vertices. Now, T has p
vertices and it is non -trivial. Hence, it has at least one leaf, say at
vertex v. Then, T –vi sa g a i n a tree having p –1 (< p) vertices and q –munotes.in

Page 35

351 edges. By induction hypothesis, p –1=( q –1) + 1. Simplifying we
get p = q + 1, as required.
4.Every non -trivial graph has at least two leaves. This follows easily
from the theorem above, asdi= 2q = 2(p –1).
5.Let e = uv be any edge in tree T. Then, e has to be its cut edge, for
if not, after removing e from T, T will be connected and hence, we
will get a uv path in T –e, a contradiction to property 1 above.
6.Every non -leaf vertex of a tree is its cut vertex. For, let u be a
vertex of a tree having degree at least 2 and v and w are its adjacent
vertices. Then, uv and uw are the only paths from u to v and u to w
respectively. Hence, on removing u from the tree, it becomes
disconnected.
7.Every tree is bipartite. To see that, choose any vertex v from tree.
Now divide vertices of the tree in two sets A and B such that, uA, if d(v, u) is even and uB, if d(v, u) is odd. B y this choice,
vA. Thus, AB = V (vertex set of the tree) and AB=.
8.A graph is connected if and only if it has a spanning tree. A
spanning t ree is a connected graph. From a connected graph, delete
one edge at a time to remove cycles and we get a spanning tree.
3.2 CHARACTERISATIO NOF TREES
Theorem 3.2.1: Let G(V, E) be a graph having p vertices and q edges.
The following statements are equiv alent for G.
i.Gi sat r e e .
ii.Every two points of G are joined by a unique path.
iii.G is connected and p = q + 1.
iv.G is acyclic and p = q + 1.
v.G is acyclic and any two nonadjacent vertices of G are joined by an
edge e, then G+eh a se x a c t ly one cycle.
vi.G is connected and every edge of G is in cut edge.
This characterisation of tree can be proved from the discussion so far.
3.3 EDGE CUTS A ND BO NDS
First, we shall start with edge cuts.
Let G(V, E) be a graph and X, Y by subsets of V, not
necessarily distinct. We denote E[X, Y] to be the set of all edges of G
having one end in X and the other in Y and by e(X, Y) their number. If
X = Y, we simply write as E(X) and e(X) for E[X, X] and e(X, X). If Y
=V–X, the set E[X, Y] is called as t he edge cut associated with X and
is denoted by(X). Obviously,(X) =(V–X) and(V) =.
Let us illustrate edge cut s with an example.munotes.in

Page 36

36
G(u)(u, v)(u, x)(u, w, x)
Fig. 3.3
The minimal edge cut of a grap h is called as bond, thus bond is
an edge cut such that none of its edge -subset is an edge cut. To
illustrate, let us have a look at the following figure.
G(V, E)(u, v, x)(u, v, x)(u, y) (not cut)
In the Fig. 3.4,(u, v, x) is a bond whereas(u, y) is not as it
has a subset which is an edge cut.
Now we shall di scus two important results associated with edge cuts.
3.4 GRAPHS A ND VECTOR SPACE
Before, we define a vector space on graph, let us first define a
binary operation -symmetric difference (denoted by), on graphs. Let
G(V, E) be a graph, having p vertices and q edges.
Let E = {e 1,e2, ...., e q}. Let E 1and E 2be two subsets of E. We
define, E 1E2as:
E1E2=E 1E2–E1E2.T hus, for a graph in Fig. 3.5 below,
we shall illustrate.
Fig. 3.5munotes.in

Page 37

37
E1 E2 E1E2
Fig. 3.6
Fig. 3.5 shows a graph on 8 vertices and 10 edges. E 1and E 2
are two subsets of edge set E of the graph. Then the Fig. 3.6 shows
E1E2.
E1= {e 1,e2,e4,e5}, E 2= {e 2,e5,e7,e8}, then E 1E2= {e 1,e4,
e7,e8}
Notations :If X and Y are two subsets of edge set E of a graph G(V,
E), having p vertices and q edges, we associate vectors X = (x 1,x2, ...,
xq) and Y = (y 1,y2, ..., y q), such that, x i= 1, y j=1 ,i fe d g ex iX, edge
yjY, else x i= 0, y j= 0. We define operationon the elements of X,
Y with a rule: 11 = 0, 00 = 0, 10 = 1 and 01 = 1. Thus, for
the edge sets E 1and E 2in the example above, we have, vector E 1= (1,
1, 0, 1, 1, 0, 0, 0, 0, 0) and vector E 2= (0, 1, 0, 0, 1, 0, 1, 1, 0, 0) and
hence vector E1E2 = (1, 0, 0, 1, 0, 0, 1, 1, 0, 0). Thus, E1E2 = {e 1,
e4,e7,e8}, as we have obtained earlier.
Thus, the q -vector representing the symmetric difference of q -
vectors E 1and E 2is in fact the q -vector of symmetric difference of E 1
and E 2. But, E 1and E 2are two subgraphs of G. Henc e, we have defined
binary operation on the subgraphs and also represented these
subgraphs in the form of a vector. The set of all 2 q q -vectors, (all
zeros indicate null graph), is a set of all edge induced subgraphs of G.
We denote it by(G). This set forms a vector space on the field GF(2)
or Z 2. This can be easily verified.
1.(G) is an a belian group under.
a. Let X, Y be any two vectors (edge sets) in(G). Then, XY is also
a vector in(G), and hence(G) is closed under(G).
b. Vector associated withis (0, 0, .. .., 0) and X(0, 0, ...., 0) = X =
(0, 0, ...., 0). Thus, identity exists.
c. If X is any edge vector, then, XX = 0 (zero vector). This shows
the existence of inverse with respect to.
d. The operationis clearly commutative.
2. Scalar multiplication on vectors is distributive.
3. Scalar multiplication is associative.
Also observe that vectors (1, 0, 0, ..., 0) associated with edge
set {e 1}, (0, 1, 0 , ...., 0) associated with edge set {e 2}, ...., (0, 0, ...., 0,
1) associated with edge set {eq}, forms a basis for the vector space.
Thus, the dimension of the vector space(G) is q.
Definition 3.3.1: Fundamental Cycle: Let T b e any spanning tree of a
connected graph G.munotes.in

Page 38

38Adding just one edge to a spanning tree will create a cycle;
such a cycle is called a fundamental cycle with respect to a spanning
tree T.
There is a distinct fundamental cycle for each edge; thus, there
is a o ne-to-one correspond ence between fundamental cycles and edges
not in the spanning tree. For a connected graph with p vertices, any
spanning tree will have p −1 edges, and thus, for a graph of q edges
and any one of its spanning trees will have q −p + 1 fundamental
cycles.
Fig. 3.7
Note: Number on the edge indicate just an edge number, so 3 means e 3.
In the above Fig. 3.7, T is a spanning tree of graph G and C 3,C6,C7
and C 8are fundamental cycles of G with respect to T. (C iis obtained
from T by adding an edge e i).
For any given spanning tree the set of all q −p + 1 fundamental cycles
forms a cycle basis, a basis for the cycle subspace of(G).
3.5 CAYLEY’S FORMULA
Cayley's formula counts the number of labelled trees on n
vertices. In other words, it counts the number of spanning trees of a
complete graph K n. However, it does not count the number of non -
isomorphic trees on nvertices.
Before we proceed to the formula, let us find number of
labelled trees for small values of nsuch as 2, 3, 4 and then we shall
generalise using Cayley’s formula.munotes.in

Page 39

39
Fig. 3.8
Let Tn denote number of labelled trees on n vertices. Then, Cayley’s
Formula states that:
Tn=nn–2.
Now let us count number of labelled trees on n vertices. In fact,
Cayley’s formula gives this count and many proofs of the formula are
available. We shall use the simplest algorithm for counting that is
“Prüfer Encoding”. Before we proceed to the proof of the formula, let
us understand “Prüfer Encoding”.
Prüfer Encoding:
The mos t straight forward method of showing that a set has a
certain number of elements is to find a bijection between that set and
some other set with a known number of elements. In this case, we are
going to find a bijection between the set of Prüfer sequences and the
set of spanning trees.
A Prüfer sequence is a sequence of n–2 numbers, each being
one of the numbers from 1 to n. We observe that, there are nn–2Prüfer
sequences for any given n, where we allow repetitions. The following
is an algorithm that ca n be used to encode any tree into a Prüfer
sequence. Let T nbe a set of all trees on nvertices.munotes.in

Page 40

40Algorithm (Coding):
1.Take any tree, t ∈Tn, whose vertices are labelled from 1 to nin
any manner.
2.Let i = 1, t 1=t .
3.From t i, choose vertex vwith the smallest label whose degree is
equal to 1, and write down the value of its only neighbour, say a i
(1in–1) (We have already shown that any tree must have at
least two leaf vertices).
4.Construct tree t i+1from t iby removing vertex vand edge va i.
5.Update itoi+ 1. Repeat from step 3 for the new, smaller tree.
Continue until only one vertex remains.
6.Drop last neighbour from the list to get a sequence of n–2
vertices. (In fact, we observe that the last in the least is always the
vertex with the highest label.)
Now, we shall apply this algorithm to a tree on 8 vertices be low.
Fig. 3.9
Step 1: Remove vertex v = 1 and a 1=2
Step 2: Remove vertex v = 2 and a 2=4
Step 3: Remove vertex v = 3 and a 3=4
Step 4: Remove vertex v = 6 and a 4=4
Step 5: Remove vertex v = 4 and a 5=5
Step 6: Remove vertex v = 7 and a 6=5
Step 7: Remove vertex v = 5 and a 7=8
Now, as per the algorithm, we have to drop a7 = 8 and hence
the Prüfer sequence is: {2, 4, 4, 4, 5, 5}.
We observe that the vertex label frequency in the sequence is
deg (vertex) –1. Also a vertex with degree one nev er appears in the
sequence.munotes.in

Page 41

41Thus, we have seen how to construct a Prüfer Sequence from a tree.
Now is the time to construct a tree from a given Prüfer sequence P.
We shall first discuss the algorithm for the same.
Algorithm (Decoding):
1. P is given Prüfe r sequence and L = {1, 2, ...., n –1, n}.
2. Let j: First label in P and k: the least number in L that does not occur
in P.
3. Connect an edge between jandk.
4. Remove jandkfrom P and L respectively.
5. Perform steps 2 to 4, till P is non -empty.
6. The re will be exactly two numbers in L remaining. Join an edge
between these two.
Thus, we get a tree corresponding to given Prüfer sequence.
Now, let us apply it on the Prüfer sequence P = {2, 4, 4, 4, 5, 5}.
Step 1: P = {2, 4, 4, 4, 5, 5}; L = {1, 2, 3, 4 , 5, 6, 7, 8}; j = 2; k = 1
Step 3: P = {4, 4, 4, 5, 5}; L = {2, 3, 4, 5, 6, 7, 8}; j = 4; k = 2
Step 4: P = {4, 4, 5, 5}; L = {3, 4, 5, 6, 7, 8}; j = 4; k = 3
Step 5: P = {4, 5, 5}; L = {4, 5, 6, 7, 8}; j = 4; k = 6
Step 6: P = {5, 5}; L = {4, 5, 7, 8}; j = 5; k = 4
Step 7: P = {5}; L={5, 7, 8}; j = 5; k = 7
Step 8: P =; L = {5, 8}
Step 9: Connect edge 5 -8.
Fig. 3.10
Following the above steps, we have now reconstructed our
original tree on 8 vertices, as in Fig. 3.9. It may be oriented differently,
but all of the vertices are adjacent to their correct neighbours, and so
we have the correct tree back. Since there were no ambiguities on howmunotes.in

Page 42

42to encode the tree or decode the sequence, we can see that for every
tree there is e xactly one corresponding Prüfer Sequence, and for each
Prüfer Sequence there is exactly one corresponding tree. More
formally, the encoding function can be thought of as taking a member
of the set of spanning trees on n vertices, Tn, to the set of Prüfer
Sequences with n −2 terms, Pn . Decoding would then be the inverse of
the encoding function, and we have seen that composing these two
functions results in the identity map. If we let f be the encoding
function, then the above statements can be summarized as follows:
f: T n→ Pn,f−1:Pn→ Tn, and f−1◦ f = I.
Since we have found a bijective function between Tn and Pn ,
we know that they must have the same number of elements. We know
that |Pn| = nn–2, and so |Tn| = nn–2.
3.6 MI NIMAL COST SPA NNING TREE A ND
KRUSKAL’S ALG ORITHM
In many real life problems in Graph Theory, such as,
networking, travelling salesman, it is necessary to find the minimum
cost spanning tree of a graph, where, weight is some value associated
with the graph, which may represent distance, cost etc.
One of the popular algorithms is credited to Kruskal, which
finds minimum cost spanning tree for a given connected graph. We
shall look at the algorithm for a weighted, connected graph G.
Like Dijkstra’s algorithm, it also follows greedy approach. The
fundamental idea behind Kruskal’s algorithm is very simple. Start with
a null graph. At each step, choose an edge which is not added so far
and has the least weight. If this edge forms a cycle then look for the
other edge else add this chosen edge.
Algorith m:The Kruskal Algorithm
Input: a weighted connected graph G = (G, w)
Output: an optimal tree T = (V,T) of G, and its weight w(T)
1:set T :=, w(T) := 0 (T denotes the edge set of the current graph)
2:while there is an edg ee∈E\T such that T ∪{e} is the edge set
of a graph do
3:choose such an edge e of minimum weight
4:replace T by T ∪{e} and w (T) by w (T) + w(e)
5:end while
6:return ((V, T), w(T))
Let us apply Kruskal’s algorithm to get the minimum cost
spanning tree as in Fig.3.11.munotes.in

Page 43

43
Fig. 3.11
1. T =,w ( T )=0
2. T = {12}, w(T) = 1
3. T = {12, 23}, w(T) = 3
4. T = {12, 23, 67}, w(T) = 6
5. T = {12, 23, 67, 45}, w(T) = 9
6. T = {12, 23, 67, 45, 14}, w(T) = 13
7. Note: Though wt( edge2 -5) is 4, it is not chosen as it forms a cycle
8. T = {12, 23, 67, 45, 14, 47}, w(T) = 17
9. Done
Fig. 3.12
Following theorem proves correctness of Kruskal’s algorithm.
Theorem 3.5.1: Minimal cost spanning tree, generated by Kruskal’s
algorithm i s optimal.
Proof: Let T be the spanning tree for G generated by Kruskal's
algorithm. Let T’ be a
minimum cost spanning tree for G. Show that both T and T’ have the
same cost. If edges of T and T’ are the same, we are done. Let E(T)E(T’).
Let e be a minimum cost edge such that eE(T’) and eE(T).
On including e in E(T’), cycle is created. Let ee 1e2...ekbe the cycle
created. This cycle should have an edge, say e j, which does n ot belong
to T. Now, w(e j)w(e), else Kruskal’s algorithm would select this
edge. Consider tree T’’ = E(T’){e}–{ej}. (Here cycle created by e
is broken by ej to get another spanning tree T’’). Also ,w ( T ’ ’ )w(T’),
which does not have e. Repeat this process for all such edges in T –T’
to eventually get T from T’ without changing the weight. Thus, T is
optimal.munotes.in

Page 44

443.7 ROOTED A ND BINARY TREES
A rooted tree T(x) is a tree T wi th a specified vertex x, called
the root of T. An orientation of a rooted tree in which every vertex but
the root has in -degree one is called a branching. We refer to a rooted
tree or branching with root x as an x -tree or x -branching, respectively.
Fig.3.13
In the Fig. 3.13 above, R is root having in -degree 0 and out -degree 3.
The vertices a1, a2 and a3 have in -degree 1 and out -degrees 2, 1 and 3
respectively. Vertices l1, l2, l3, l4, l5 and l6 have in -degree 1 each and
out-degree 0. Vertices having ou t degree 0 are termed as leaves.
Vertices a1, a2 and a3 are called as children of R and R is the
parent of these vertices. Vertices a1, a2 and a3 are siblings, as they
have same parent.
Thus, rooted tree is a directed graph.
Binary trees are special ki nd of rooted trees. In binary trees there are
maximum 2 children to any vertex. Vertex having no child is as before
termed as leaf.
Fig. 3.14(a) Fig. 3.14(b)
Rooted trees and branching are effective too ls in designing of
efficient algorithms for the purpose of reachability. There are certain
terminologies exclusively associated with rooted binary trees.
The depth of a node is the number of edges from the root to the
node.munotes.in

Page 45

45The height of a node is the num ber of edges from the node to the
deepest leaf.
The height of a tree is a height of the root. (Thus, height of tree in
Fig. 3.14(a) is 2)
A complete binary tree is a binary tree, which is completely filled,
with the possible exception of the bottom level, which is filled
from left to right. (Fig. 3.14(b))
As graphs and trees have many real life applications, the vertices
are usually used to store some data and we may need to search or
traverse to the node to access the data. Hence, traversal is of utmost
importance in graphs and trees. Now, shall look at some algorithms for
the tree and graph traversals.
3.7.1 Breadth First Search:
In most types of tree -search, the criterion for selecting a vertex
to be added to the tree depends on the order in which the v ertices
already in the tree T were added. A tree -search in which the adjacency
lists of the vertices of T are considered on a first -come -first-served
basis, that is, in increasing order of their time of incorporation into T,
is known as breadth -first searc h. In order to implement this algorithm
efficiently, vertices in the tree are kept in a queue; this is just a list Q
which is updated either by adding a new element to one end (the tail/
rear of Q) or removing an element from the other end (the head/front
of Q). At any moment, the queue Q comprises all vertices from which
the current tree could potentially be grown.
Initially, at time t = 0, the queue Q is empty. Whenever a new
vertex is added to the tree, it joins Q. At each stage, the adjacency list
of the vertex at the head of Q is scanned for a neighbour to add to the
tree. If every neighbour is already in the tree, this vertex is removed
from Q. The algorithm terminates when Q is once more empty. It
returns not only the tree (given by its predecessor f unction p), but also
records the level of each vertex in the tree and, more importantly, their
distances from r in G. It also returns a function t which records the
time of incorporation of each vertex into the tree T. We keep track of
the vertices in T by colouring them black. The notation G(x) signifies a
graph G with a specified vertex (or root) x. Recall that an x -tree is a
tree rooted at vertex x.
Algorithm: Breadth -First Search (BFS)
Input: a connected graph G(r)
Output: an r-tree T in G with prede cessor function p, a level function
l, such that l(v) = dG(r,v) for all v ∈V , and a time function t
1: set i := 0 and Q :=2: increment i by 1
3: colour r black
4: set l(r) := 0 and t(r) := i
5: append r to Q
6: while Q is non empty do
7: consider the head x of Q
8: if x has an uncoloured neighbour y then
9: increment i by 1munotes.in

Page 46

46138 6 Tree -Search Algorithms
10: colour y black
11: set p(y) := x, (y) := (x) + 1 and t(y) := i
12: append y to Q
13: else
14: remove x from Q
15: end if
16: end while
17: return (p,l, t).
Before we discuss the algorithm in detail, let us first implement it on
the following graph.
Fig. 3.15
Now, let us apply BFS on the Fig. 3.15.
munotes.in

Page 47

47Q:11212312341234523452345623456734567345678345678945678945678910567891056789101167891011678910111278910111289101112910111291011121310111213111213121313.
Based on this, the highlighted edges in the Fig. 3.15 show the BFS
tree.
3.7.2 Depth -First Search
Depth -first search is a tree -search in which the vertex added to
the tree T at each stage is one which is a neighbour of as recent
addition to T as possible. In other words, we first scan the adjacency
list of the most recently added vertex x for a neighbour not in T. If
there is such a neig hbour, we add it to T. If not, we backtrack to the
vertex which was added to T just before x and examine its neighbours,
and so on. The resulting spanning tree is called a depth -first search tree
or DFS -tree.
This algorithm may be implemented efficiently by maintaining
the vertices of T whose adjacency lists have yet to be fully scanned,
not in a queue as we did for breadth -first search, but in a stack. A stack
is simply a list, one end of which is identified as its top; it may be
updated either by adding a new element as its top or else by removing
its top element. In depth -first search, the stack S is initially empty.
Whenever a new vertex is added to the tree T, it is added to S. At each
stage, the adjacency list of the top vertex is scanned for a neighb our to
add to T. If all of its neighbours are found to be already in T, this
vertex is removed from S.
The algorithm terminates when S is once again empty. As in
breadth -first search, we keep track of the vertices in T by colouring
them black. Associated with each vertex v of G are two times: the time
f(v) when v is incorporated into T (that is, added to the stack S), and
the time l(v) when all the neighbours of v are found to be already in T,
the vertex v is removed from S, and the algorithm backtracks to p(v),
the predecessor of v in T. The time increments by one with each
change in the stack S. In particular, f(r) = 1, l(v) = f(v) + 1 for every
leaf v of T, and l(r) = 2n.
Algorithm: Depth -First Search
Input: a connected graph G
Output: a rooted spanni ng tree of G with predecessor function p, and
two time functions f and l.
1: set i := 0 and S :=2: choose any vertex r (as root)
3: increment i by 1
4: colour r black
5: set f(r) := i
6: add r to S (that is push r on stack S)
7: while S is nonempty do
8: consider the top vertex x of S
9: increment i by 1munotes.in

Page 48

4810: if x has an uncoloured neighbour y then
11: colour y black
12: set p(y) := x and f(y) := i
13: add y to the top of S (that is push y on stack S)
14: else
15: set l(x) := i
16: remove x from S (that is pop x from the stack S)
17: end if
18: end while
19: return (p, f, l)
Now, let us apply DFS above for the graph below:
Highlighted edges in the graph indicate DFS tree.
Fig. 3.16
Note: Unused columns are used to indicate push and pop.munotes.in

Page 49

493.8HUFFMA NCODES
In Computer Science, it is required to encode the text into a bit -
string. Suppose, we want to encode all the alphabets in English (where
no distinction is made between lowercase and uppercase letters). We
can represent ea ch letter with a bit string of length five, because there
are only 26 letters and there are 32 bit strings of length five (E.g.
00000, 00001, 00010, so on, the count is 25). The total number of bits
used to encode data is five times the number of character s in the text
when each character is encoded with five bits. Is it possible to find a
coding scheme of these letters such that, when data are coded, fewer
bits are used? We can save memory and reduce transmittal time if this
can be done.
We now introduce an algorithm that takes as input the
frequencies (which are the probabilities of occurrences) of symbols in
a string and produces as output a prefix code that encodes the string
using the fewest possible bits, among all possible binary prefix codes
for the se symbols. This algorithm, known as Huffman coding, was
developed by David Huffman. This algorithm assumes that we already
know how many times each symbol occurs in the string, so we can
compute the frequency of each symbol by dividing the number of
times this symbol occurs by the length of the string. Huffman coding is
a fundamental algorithm in data compression, the subject devoted to
reducing the number of bits required to represent information.
Huffman coding is extensively used to compress bit string s
representing text and it also plays an important role in compressing
audio and image files. Given symbols and their frequencies, our aim is
to construct a rooted binary tree where the symbols are the labels of the
leaves. The algorithm begins with a fore st of trees each consisting of
one vertex, where each vertex has a symbol as its label and where the
weight of this vertex equals the frequency of the symbol that is its
label. At each step, we combine two trees having the least total weight
into a single tree by introducing a new root and placing the tree with
larger weight as its left subtree and the tree with smaller weight as its
right subtree. Furthermore, we assign the sum of the weights of the two
subtrees of this tree as the total weight of the tree . The algorithm is
finished when it has constructed a tree, that is, when the forest is
reduced to a single tree.
Algorithm: Huffman Code:
Input: Huffman(C: symbols a iwith frequencies w i, i = 1, . . . , n)
F := forest of nrooted trees, each consisting of the single vertex a iand
assigned weight w i
Output: Huffman code of every symbol
Procedure:
while F is not a tree
Replace the rooted trees T and T’ of least weights from F with
w(T ) ≥w(T’) with a tree having a new root that has T as its left
subtr ee and T’ as its right subtree.
Label the new edge to T with 0 and the new edge to T’ with 1.
Assign w(T ) + w(T’) as the weight of the new tree.munotes.in

Page 50

50End while;
Assign the Huffman code for the symbol ai as the concatenation of the
labels of the edges in theunique path from the root to the vertex ai.
Let us understand the algorithm better with the help of an example.
Use Huffman coding to encode these symbols with given frequencies:
a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30, f: 0.12. What is the average
number of bits required to encode a character?
In the Step V, we get the necessary coding tree. The codes are as
below:
a: 000; b: 111; c: 001; d: 10; e: 01; f: 110
Average number of bits required is:
3x0.2 + 3 x0.1 + 3 x0.15 + 2 x0.25 + 2 x0.3+3 x0.12 = 2.81
Note that Huffman coding is a greedy algorithm. Replacing the two
subtrees with the smallest weight at each step leads to an optimal code
for these symbols can encode these symbols using fewer bits.
Solved Problems:
1. The complete bi partite graphs K1,n, known as the star graphs. Prove
that the star graphs are the only complete bipartite graphs which are
trees.
Solution: The number of edges in a star graphs is n –1. Also one
partite has 1 vertex and the other has n vertices, no two ve rtices in the
second partition can be connected and hence star graph is acyclic and
connected. Thus, it is a tree. N Now, in Km, n, with m, n > 0 degree of
every vertex is at least two. Hence it has a cycle. So it cannot be a tree.munotes.in

Page 51

513.9UNIT END EXERCISES :
1. Let G be a connected graph which is not a tree and C be a cycle in
G. Prove that complement of any spanning tree of G contains an edge
of C.
2. Prove Theorem 3.2.1.
3. Find minimum cost spanning tree for the following graph using
Kruskal’s algorithm.
4. Like Kruskal’s algorithm, Prim’s algorithm too find minimum cost
spanning tree. However, in Prim’s algorithm, at every step, we add an
edge having least cost provided when an edge is added cycles is not
formed. (E.g. in the above graph, we start wit h edge CD, followed by
CB, BA, DF, however, AD is not chosen as a cycle is formed.) Find
minimum cost spanning tree for the following graph using Prim’s
algorithm.
munotes.in

Page 52

525. Draw BFS tree for the following graph.
6. Draw DFS tree for the following graph.
7. Use Huffman coding to encode these symbols with given
frequencies: A: 0.10, B: 0.25, C: 0.05, D: 0.15, E: 0.30, F: 0.07, G:
0.08. What is the average number of bits required to encode a symbol?
8. Find Prüfer sequence for the tree below.
9. Decode the Prüfer sequence (1, 1, 1, 1, 6, 6, 5)
munotes.in

Page 53

534
EULERIA NAND HAMILTO NIAN
GRAPHS
Unit Structure:
4.0 Objectives
4.1 Introduction
4.2 Randomly Eulerian Graphs
4.3 Chinese Postman Problem
4.4 Hamiltonian Graph
4.5 Degree Majorisation
4.6 Travelling Salesman’s Problem:
4.7 Unit End Exercises
4.0 OBJECTIVES
1.Definition and characterisation of Eulerian graph
2.Fleury’s algorithm
3.Application of Eulerian graph: Chinese postman’s problem
4.Definition of Hamiltonian graph
5.Sufficient and necessary conditions for Hamiltonian graphs
6.Degree majorisation
7.Application of Hamiltonian graph: Travelling salesman’s problem
4.1INTRODUCTIO N
In chapter one, we have seen that the Konigsberg’s bridge
problem, devised by Euler, gave birth to Graph Theory. While proving
non-existence of the necessary path, Euler defined a class of graphs,
which are now termed as Eulerian graphs. In this chapter, we shall
discuss Eulerian graphs in detail.
Speaking plainly, in a graph, if you start from any vertex and
without lif ting your pencil and traversing all the edges exactly once, if
you can come back to the starting vertex, you have come across an
Eulerian graph and you have traversed an Eulerian circuit. To explain
further, let us have a look at the graph if Fig. 4.1 belo w.munotes.in

Page 54

54
Fig. 4.1
In the Fig. 4.1 above, if we start at vertex v1, we can take the
route as v1v2v3v4v5v6v3v1. Thus, the graph of Fig. 1.4 is Eulerian. Now,
let us define Eulerian graphs formally.
Definition 4.1.1: Eulerian Trail: In a connected graph G, a path that
visits every edge exactly once is termed as an Eulerian Trail.
Definition 4.1.2: Eulerian Circuit: In a connected graph G, circuit in
which every edge is traversed exactly once is termed as Eulerian
circuit.
Definition 4.1.3: Eulerian Graph: A connected graph having Eulerian
circuit is called as Eulerian graph.
The graph in Fig. 4.1 is Eulerian.
A traversable graph is one that can be drawn without taking a
pen from the paper and ithout retracing the same edge. In such a case
the graph is said to have an Eulerian trail.
Characterisation of Eulerian graph:
While showing that there no path that crosses all the bridges
exactly once, in the Konigsberg’s bridge problem, Euler represented
the bridges in the form of a graph as we have seen in Fig. 1. 2. He
stated that any graph to be traversed in this manner has to be even.
Thus, we have a very important property of Eulerian graph as below:
Theorem 4.1: A graph is Eulerian if and only if it is connected and
even.
Proof: Suppose a graph G is Eulerian. Since G is Eulerian, it has
Eulerian circuit and Eulerian circuits are connected. Hence, G is
connected. Now, let v be any vertex in G. Let us traverse Eulerian
circuit from v. For traversing all the edges, a vertex is entered and left,
contributing two t o the degree of any vertex. This is true whenever we
traverse a vertex (note that a vertex may occur multiple times in the
Eulerian circuit). At the end, we return to v, contributing two to degree
of v as well. Thus, degree of every vertex is even.
Conver sely, let G be even and connected graph. We shall prove
that it is Eulerian, that is it has an Eulerian cicuit. Suppose that graph G
is connected and its all the vertices are even. If there is more than one
vertex in G, then each vertex must have degree gr eater than 0. Begin atmunotes.in

Page 55

55a vertex v. As we know, a graph with even vertices partitions into
cycles (Theorem 1.4.3), we know that v will be on at least one cycle.
Since G is connected, there must be an edge {v, v1} for some vertex
v1≠v. Since v1 has even degree greater than 0, there is an edge {v1,
v2} where v2 ≠ v1. These two edges make a trail from v to v2.
Continue this trail, leaving each vertex on an edge that was not
previously used, until returning to v. This is always possible, because v
is on a cycle. Call the circuit (cycle is a circuit) formed by this process
C1. If C1 covers all the edges of G, then we are done. Otherwise,
remove all the edges that contribute to C1 from G, leaving the graph
G0. The remaining vertices are still even, and since G is c onnected
there is some vertex u in both G0 and C1. Repeat the same process as
before, beginning at u. The new circuit, C2, can be added to C1 by
starting at v, moving along C1 to u, travelling around C2 back to u and
then along the remainder of C1 back to v. Repeat this process, adding
each new circuit found to create a larger circuit. Since G is finite, this
process must end at some point, and the resulting circuit will be an
Eulerian circuit.
If an Eulerian graph is small then in general it is straight
forward to find an Eulerian circuit. But that need not be the case
always. In such situation Fleury’s algorithm comes to help us. It finds
Eulerian circuit, given any Eulerian graph.
The basic idea behind Fleury’s algorithm is very simple. Start
with any v ertex u, the next vertex v is chosen in such way that uv is not
a bridge unless there is no other option. Let us first write down the
steps of the algorithm and then apply on the graph of Fig. 4.1.
Fleury’s Algorithm:
Input: A connected even graph G and a vertex u of G
Output: An Eulerian circuit C of G starting (and ending) at u
1: set C := u, x := u, F := G
2: whi le∂F (x) do
3: choose an edge e := xy∂F (x), where e is not a cut edge of F
unless there is no alternative
4: replace uCx by uCxey, x: = y, and F:= F –e
5: end while
6: return C
Let us apply the algorithm on Fig, 4.1.
munotes.in

Page 56

56
In the last step we get the necessary Eulerian circuit:
v1v3v4v5v6v3v2v1.
Following theorem gives the proof of correctness of Fleury’s
algorithm.
Theorem 4.2: If G is an even and connected graph, then t he circuit C,
returned by Fleury’s algorithm is an Eulerian circuit.
Proof: The sequence C is initially a trail, and remains one throughout
the procedure because Fleury’s Algorithm always selects an edge of F
(that is, an as yet unchosen edge) which is in cident to the terminal
vertex x of C. Moreover, the algorithm terminates when ∂F(x) =, that
is, when all the edges incident to the terminal vertex x of C have
already been selected. Because G is even, we deduce that x = u; in
other words, the trail C returned by the algorithm is an Eulerian circuit.
Now, we shall show that C has all the edges of G. Let us
assume contrary.
Let C = { v0v1v2....v kvk+1....v nv0}. Let F = G –E(C).E(F). Hence there are vertices of positive degree in F. In fact
every vertex in F has even degree, since F is obtained from G by
deleting edges of a circuit. Let S = {vF: degF(v) > 0}. Let H be a
subgraph of G induced by the vertex set S. Then, v 0V–S, as we
terminate the algorithm onceF(v0)=.munotes.in

Page 57

57Graph induced by S Graph induced by V –S
Fig. 4.2
Let vk be the l ast vertex in C such that v kS. Then v k–1V–S
and e k+1=v kvk+1is the only edge joining S induced subgraph and V –S
induced subgraph. Therefore, i. e k+1is a bridge in F.
Next, since every vertex of H has positive degree, there exists
an edge e, incident with vk in H. It is not a bridge of H since every
vertex of H has even degree. Hence e is not a bridge of F either as
HF. Now, while executing (k+1)th iteration, we preferred to choose
ek+1to e, thus ii. e k+1is not a bridge in F (by Fleury’s rule).
(i) and (ii) contradict. (Refer Fig. 4.2)
4.2RANDOMLY EULERIA NGRAPHS
We have seen the traceability of Eulerian graph. In fact,
Fleury’s algorithm gives a systematic way of tra versing an Eulerian
graph to get an Eulerian circuit. Now, let us look at a very interesting
class of Eulerian graph and that is randomly Eulerian graph.
An eulerian graph G is randomly Eulerian from a vertex v of G
if the following procedure always resul ts in an eulerian circuit of G:
Begin a trail at v by choosing any edge incident with v. Next
(and at each step thereafter), the trail is continued by selecting any
edge not already chosen which is adjacent with the edge most recently
selected. The proces s terminates when no such edge is available.
Equivalently, a graph G is randomly Eulerian from v if every trail of G
beginning at v can be extended to an Eulerian circuit of G.
Before, we proceed to prove the results about randomly
Eulerian graphs, let us look at the examples of Eulerian graphs which
are (or are not) randomly Eulerian.munotes.in

Page 58

58
Fig. 4.3
In the graphs of Fig. 4.3, we observe that, G0 is not randomly
Eulerian, G1 is randomly Eulerian only from u3, G2 is randomly
Eulerian from u1 and u6 and G3 i s randomly Eulerian from all its
vertices.
Explanation:
1. In G0, trail u1u2u3u5u4u3u1u5u6u4u2cannot be extended to Eulerian
circuit.
2. In G1, trail u1u2u3u1 cannot be extended to Eulerian circuit.
3. In G2, trail u2u6u3u1u2 cannot be extended to Euleri an circuit.
(Note: The trick for verification is very simple. While applying
Fleury’s algorithm to find Eulerian circuit, if bridge is encountered
then traverse the bridge instead of other non -bridge option.)
Theorem 4.3: An Eulerian graph G is randomly Eulerian for a vertex v
if and only if v is on every cycle of G.
Proof: Since Eulerian graph is even, it can be partitioned into cycles
(Theorem 1.4.3).
Let G be randomly Eulerian for a vertex v. Let, if possible, there is a
cycle C of which does not con tain v. Let G1 = G –C. Since G and C
are Euler graphs, so is G1 (as it too will have all vertices of even
degree). G1 need not be connected but it should have a maximal
connected component G(v) that includes vertex v. Then the sum, G2 =
G(v) + C has to be connected Eulerian graph.
With this background, we shall observe the following properties.
1. An Eulerian graph G is randomly Eulerian for a vertex v if and only
if v is on every cycle of G.munotes.in

Page 59

592. If a graph G has exactly two odd vertices u and v, then G i s
randomly traversable from u to v if and only v is on every cycle of G.
4.3 CHI NESE POSTMA NPROBLEM
A Chinese mathematician called Kuan Mei -Ko was interested
in a postman delivering mail to a number of streets such that the total
distance walked by the postman was as short as possible. How could
the postman ensure that the distance walked was a minimum?
The problem defined above is termed as Chinese Postman Problem.
In this type of problems, we can represent the route with a
graph and check if is trave rsable.
If it is an Eulerian graph then we know we can traverse easily
and the minimum distance will be same as sum of weights of all the
edges.
If the graph is not an Eulerian graph, it will have odd vertices.
We know that a graph has even number of odd vertices. So in that case
we pair up the vertices, which contribute the least distance and add up
to the total weight of the graph to get the minimum distance.
This is an idea behind the algorithm to solve the Chinese
Postman Problem.
In the following e xample a postman has to start at A, walk
along all 13 streets and return to A. The numbers on each edge
represent the length, in metres, of each street. The problem is to find a
trail that uses all the edges of a graph with minimum length.
Before we proce ed to solve the problem, let us have a look at
the pre -requirements for the algorithms and then the steps of the
algorithm.
We have seen that any graph as even number of odd vertices.
Let us find out how many pairs are possible when there are 2 nodd
vertices.
1. Suppose there are 2 odd vertices a 1and a 2. Then only one pair is
possible.
2. Suppose there are 4 odd vertices a1 a 2,a3and a 4. Then three pairs
are possible. E.g. {a 1a2,a 3a4}, {a 1a3,a 2a4} and {a 1a4,a 2a3}
(i.e. 3 x1)
3. Suppose there are 6 o dd vertices a 1,a2,a3,a4,a5and a 6. Then, 15
pairs are possible, as a1 can be paired with 5 other vertices and
remaining four vertices can be paired in 3 x1 pairs, so total pairs
are 5 x3x1 = 15.
4. We continue this way, for 8 odd vertices, 7 x5x3x1= 105 pairs are
possible.
5. For 2 nvertices, (2 n–1)x(2n–3)x...x3x1 pairs are possible.munotes.in

Page 60

60Now that we know how to count number of odd pairs, let us
understand the algorithm.
Algorithm:
1. List all odd vertices.
2. List all possible pairings of odd vertices.
3. For each pairing find the edges that connect the vertices with the
minimum weight.
4. Find the pairings such that the sum of the weights is minimised.
5. On the original graph add the edges that have been found in Step 4.
6. The length of an optimal Chinese postman route is the sum of all the
edges added to the total found in Step 4.
7. A route corresponding to this minimum weight can be easily found.
Let us implement the same on Fig. 4.4.
1. There are only two odd vertices, viz. A and H. So just one pair is
possible.
2. Minimum cost from A to H is 160 (A –B–F–H).
3. Draw the additional edges on the original graph along this path.
(Fig. 4.5)
4. The minimum cost for this problem is sum of all weights of original
graph and 160, which is 840 + 160 = 1000.
5. One possible path is ABEFBDACGHCDFH -FBA.
To find the route of the postman, one has to simply add the extra edges
with reference to the minimum distance so that all the vertices have
even degree and find an Eulerian circuit from the starting (odd) vertex.
munotes.in

Page 61

614.4HAMILTO NIANGRAPH
A path having connecting all the vertices of a connected graph
is called as Hamiltonian path and a cycle through all the vertices of a
graph is termed as Hamiltonian cycle. Hamilton described this graph,
inthe form of a puzzle. He drew a dodecahedron and put pins at five
consecutive vertices of the same. Other player has to put the pins to
complete a spanning cycle. A dodecahedron with its spanning cycle
(highlighted) is shown in Fig. 4.6 below.
We can m ake very interesting observations of Hamiltonian graphs.
1. A complete graph on n vertices, where n3
2. A cycle on n vertices is Hamiltonian.
3. Though every Eulerian graph need not be Hamiltonian, line graph of
a every Eulerian graph is Hamiltonian.
4. If G is Hamiltonian then the graph obtained by adding edges to non -
adjacent vertices of G, remains Hamiltonian.
5. Every non -Hamiltonian graph can be converted into Hamiltonian by
adding edges into it. (This is true because complet e graph is
Hamiltonian)
Definition: A graph G is said to be maximal non -Hamiltonian, if it not
Hamiltonian and on adding an edge between any pair of its non -
adjacent vertices, it becomes Hamiltonian.
The graph in Fig. 4.7 below is maximal non -Hamiltonian.
Fig. 4.7
Like Eulerian graph, Hamiltonian graph has no elegant
characterisation. However, there are some necessary and some
sufficient conditions to determine whether given graph is Hamiltonian.munotes.in

Page 62

62Now, we shall prove a necessary condition for a graph to be
Hamiltonian.
Theorem: If G is Hamiltonian, then for every non -empty subset
SV(G), c(G –S)|S| .( c ( G –S) is number of distinct components
obtained after removing S from G).
Proof: Let G be Hami ltonian. LetSV(G). Let wS. Let C be
Hamiltonian cycle of G beginning at w. Let c(G –S) = k.
If k = 1, then S being non -empty set we readily see t hat | S |1 = k.
Now let k > 1 and G1, G2, ..., Gk be the components of G –S.
Fig. 4.8
Before we proceed, let us give some orientation to C.
(Fig. 4.9). Let uibe the last vertex of C that belongs to G i.
Letvibe the n ext vertex of C that comes after ui(this is
possible due to the orientation given to C). Obviously, vican not
belong to G i. This is because uiis the last vertex in G i. Also vicannot
belong to any other G j, for 1jk. For else components G iand G jwill
be connected; however all the components are mutually disjoint.
Hence, viS. Also, vivj for ij. (Fig. 4.8 and Fig. 4.10). Th is is
because uiviE(G) for every i.
Therefore, for each i,viS|S|k.
munotes.in

Page 63

63Thus, we have proved a necessary condition for a graph to be
Hamiltonian. A s a result, the contra positive of this condition, “Let G
be a connected graph. If there exists a subset S of V, such that c(G –S)
> | S |, then G is non -Hamiltonian”, can be useful to show that a graph
is not Hamiltonian. We shall check this with the hel p of an example
below. (Fig. 4.11)
However, the condition that we have proved is necessary condition for
a graph to be Hamiltonian and not sufficient. The reader can verify that
Petersen’s graph satisfies the necessary condition of Theorem 4,
however t he graph is not Hamiltonian.
Now, we shall prove the sufficient conditions for a graph to be
Hamiltonian.
Dirac’s theorem gives a sufficient condition for a graph to be
Hamiltonian,
Theorem: (Dirac’s Theorem): If a connected graph G has n3 vertices
and degree of every vertex is at least , then it has Hamiltonian cycle.
Proof: We shall prove the result by contradiction. Let, if possible, G be
a graph having n3 vertices such that degree of every verte x is at least2n, but it has no Hamiltonian cycle.
Let Pp1p2...pkbe the longest path in G. If p 1is connected to a vertex
vnot on path P, then vp 1p2...pkwill be longer than P, hence p 1has all
its adj acent vertices in path P. Same argument holds true for p kas well.
Thus, p 1and p kare adjacent to vertices on P itself and not outside the
path. As deg(p 1)2nand p 1cannot be adjacent to itself k2n+1.
So we claim that there is some value of j (1jk) such that pk
is adjacent to p jand p 1is adjacent to p j+1(Fig. 4.8). Suppose the claim
is not true. Then since all the adjacent vertices of p 1lie on P, there
must be at least deg(p 1) vertices that are not adjacent to p kand
similarly there must be at least deg(p k) vertices that are not adjacent tomunotes.in

Page 64

64p1. Thus the path P must have at least deg(p1) + deg(pk) +1=n+1
vertices, which contradict that there are n vertices.
This gives us cycle C : p j+1p j+2...p k–1pkpjpj–1pj–2...p 1pj+1.
Now, we shall show that C is the Hamiltonian cycle of G.
Let, if possible, G –C is non -empty. Then, there is a vertex v in G–C
such that v is connected to C at some vertex pi (this is because G is
connected) and hence path starting from v and through pi around the
cycle C is longer than P which contradicts our choice of P.
Hence C is the necessary Hamiltonian cycle.
Thus, from the above theorem, we observe that Dirac’s theorem
gives sufficient condition for a graph to be Hamiltonian. However, this
condition is not necessary, as reader can readily see that a cycle Cn
(n5) is Hamiltonian but(Cn)=2<2n.
Definition: Closure of a Graph: Let G be a graph on n vertices. If there
is a pair of nonadjacent vertices u1andv1such that deg(u1) + deg(v1)n, then join u1andv1by an edge to form a super graph G 1of G. In
G1, if there is a pair of non -adjacent vertices u2and v2such that
deg(u2) + deg(v2)n, then join u2andv2by an edge to form a super
graph G 2of G 1.
Continue this process till no such pair exists. Then the graph so formed
is called as closure of G and is denoted by c(G).
We shall understand the definition with the help of an example in Fig.
4.9 below.
Fig. 4.13munotes.in

Page 65

65Bondy -Chvatal Theorem: Let G be a simple graph on n vertices and u
and v be nonadjacent vertices in G such that d(u) + d(v)n, then G is
Hamiltonian if and only if G + uv is Hamiltonian.
Proof: If G is Hamiltonian, then G + uv is Hamiltonian.
Conversely, let G + uv is Hamiltonian. Let, i f possible, G is not
Hamiltonian.
Since G + uv is Hamiltonian and G is not, every Hamiltonian cycle of
G + uv contains edge uv. Thus, there is a Hamiltonian path u = v 1-v2-
v3-...-vn= v in G. Define sets S and T as:
S = {v i: uv i+1E(G)} and T = {v i:vivE(G)}.
Since vST, |S U T| < n. (i.e. number of vertices in S U T is less
than n).
Also |ST| = 0, for if there is a vertex v iST, the there will be a
Hamiltonian cycle v 1v2...vivnvn–1...vi+1v 1which belongs to G, which is
not possible by our assumption.deg(u) + deg(v) = |S| + |T| = |ST|–|ST| < n.
This contradicts given condition that d(u) + d(v)n.
Thus, our assumption is wrong. Therefore, G is Hamiltonian.
Theorem: A graph G is Hamiltonian if and only i f its closure is
Hamiltonian.
Proof: If G is Hamiltonian, then obviously closure of G is Hamiltonian.
Let closure of G is Hamiltonian. Let closure of G is made by
successively adding edges uv (where d(u) + d(v)n) and we obtain a
sequence G 1,G 2, ...., G k. Then, by successively applying Theorem on
Gk, Gk –1, ..., G1, we can prove that G is Hamiltonian.
4.5DEGREE MAJORISATIO N
A sequence of real numbers (p 1,p 2, ..., p n) is said to be
majorised by another such sequence (q 1,q2,..., q n)i fp iqifor 1in.
A graph G is said to be majorised by other graph H, if |V(G)| =
|V(H)| and a non -decreasing degree sequence of G is majorised by that
of H.
As an ex ample, observe the graphs C 5and K 2, 3 of Fig. 4.14
below.munotes.in

Page 66

66
Theorem: Let G be a simple graph having degree sequence (d 1,d2, ...,
dn), where d 1d2...dnand n3. Suppose there is no value of m for
which d mm and d n–mProof: Let G be a simple graph that follows the hypothesis given in the
theorem statement.
We shall show that its closure is complete and hence by Theor em we
can say that G is Hamiltonian.
Let, if possible, closure of G, (say G’) is not complete. We shall denote
degree of a vertex v in G’ by d’(v). Let u and v be two non -adjacent
vertices in G’, such that, d'(u)d’(v) (A)
We choose these two such that d’(u) + d’(v) is as large as possible.
Since G’ is not Hamiltonian, d'(u) + d’(v) < n (B)
Now, let S be set of vertices in V –{v} which are not adjacent
to v and T be set of vertices in V–{u} which are not adjacent to u in
G’. Then we have |S|=n –1–d’(v) and | T | = n –1–d’(u) (C)
Further, by the choice of u and v, each vertex in S has degree at
most d’(u) and each vertex of T{u} has degree at most d’(v). Set m
= d’(u).
Then, by (A ), d’(v) < m –n.
By (B) and (C) S and hence G’ has at least m vertices of degree at most
m.
Also by (B) and (C), T{u} and hence G’ has n –m vertices
of degree less than n –m.
Because G is a spanning subgraph of G’, the same is true for G.
Thus, d mm and d n–mn–m. But this is contrary to the
hypothesis since by (A) and (B), m < n/2. Hence, G’ is complete and G
is Hamiltonian.
Now we shall prove a very important theorem a bout
Hamiltonian graphs by Chvátal.
Before we proceed, let us first introduce the notion of “join” of
two graphs.munotes.in

Page 67

67Let G and H be two disjoint graphs. Join of G and H, denoted
by G  H, is obtained byconnecting every vertex of G to each and
every vertex of H.
Now, for 1m < n/2, define C m,na s2Cmm n mKK K .F o r
example1,5 1 1 3CCKK Kand2,5 2 2 1CCKK Kare shown
in Fig.4.15.
We observe that Cm, n is non -Hamiltonian. This is because, if
we take set S to be a set of m vertices having degree n –1, (e.g. K m),
then on removing S from C m,n,w eg e tm+ 1components. Thus, by
contra positive of Theorem (necessary condition for a graph to be
Hamiltonian), we see that C m,nis non -Hamiltonian.
Theorem: (Chvátal’ theorem): If G is non Hamiltonian simple graph
with n3 then G is degree majorised by some C m,n.
Proof: Let G be a non Hamiltonian simple graph with degree sequence
(d1,d2, ..., d n), where d1d2... d nand n3. Then by Theorem, there
exists m < n /2 such that d mm and dn–mn–m. Therefore, (d 1,d2, ...,
dn) is majorised by the sequence (m, ...,m, n –m–1, ..., n–m–1, n–
1, ..., n –1) with m terms equal to m (contribution fromCmK), n–2m
terms equal to n –m (Contribution from K n–2m) and m terms equal to n
–1 (Contribution from K m),which is a degree sequence of C m, n.
Theorem: If G is a simple graph with n3, such that 12nEG,
then G is Hamiltonian. In fact, only non Hamiltonian simple graphs
having n vertices and12nedges are C 1, nand for n = 5, C 2, 5.
Proof: Let G be a non Hamiltonian graph. Then we shall show that
E(G) is at most12n.Since G is non Hamiltonian, it degree
majorised by some C m, nby Chvátal’s theorem. Hence,
munotes.in

Page 68

68If we observe (A), equality holds if m = 1 and for m = 2, n = 5
and hence G has same degree sequence as that of C 1, nand C 2,5
respectively . In both the cases,1,nGCor2,5GC.
Thus, from the above result, we say that maximum number of
edges in a simple non Hamiltonian graphs having n vertices, is
112n.
4.6TRAVELLI NG SALESMA N’S PROBLEM:
Now, we shall look at an important application of Hamiltonian
graph that is Travelling salesman’s problem.
A travelling salesman wishes to visit a number of towns and
return to his starting point.
Given the travelling times between two towns , how should he
plan his itinerary so that he visits each town exactly once and travels
for the least time? In graphical terms, we have to find the minimum
weight Hamiltonian cycle in a weighted complete graph.
In contrast to the Chinese Postman Problem, there is no
efficient algorithm to solve travelling salesman’s problem.
The approach can be start with any vertex and find all possible
Hamiltonian cycles from that vertex and find total cost for each of the
cycle. However, this approach needs (n –1)!computations which is
very large as value of n gets moderately big. Hence the approach is not
practicable.
In the light of above discussion, what we try to find is a
reasonably good (not necessarily an optimal) solution.
Fig. 4.16munotes.in

Page 69

69Let us represent the a bove graph in the form of matrix.
Now, let Hamiltonian cycle begins at A. So from A we choose
a vertex which is at the minimum distance, so it D, in this problem.
Now scan D’s row for the least weight. It is 36 for C (we cannot
choose 2, as A is chosen) . We keep on scanning next row for the least
possible weight value, avoiding earlier chosen vertex or formation of
cycle that has less number of vertices than a complete cycle.
A cycle that is obtained for the problem of Fig.4.16 is A -D-C-
B-F-E-A having r easonably optimal weight as 191.
Please note that this may not be an actual optimal weight.
4.7UNIT END EXERCISES:
1. Ore’s Theorem states that “If a connected graph G has n3 vertices
and for every pair u, v of non -adjacent v ertices, deg(u) + deg(v)n,
then G is Hamiltonian”. Prove this theorem.
2. Give two examples of maximal non -Hamiltonian graphs.
3. Draw a graph corresponding to the following degree sequences or if
no graph exists, justify:
(i) (2, 2, 2, 2)
(ii) (1, 2, 3, 4)
(iii) (2, 2,3, 3)
(iv) (1, 1, 1, 2)
4. Prove or disprove: Two graphs with the same degree sequence are
isomorphic.
munotes.in

Page 70

5
Matching and Ramsey
Theory
Unit Structure :
5.1I n t r o d u c t i o n
5.2M a t c h i n gI nB i p a r t i t eG r a p h s
5.3I n d e p e n d e n ts e t sa n dc o v e r i n g
5.4 The Personnel Assignment Problem
5.5 Ramsey Number
5.6 Unit End Exercise
5.1 INTRODUCTION
Matching theory is used to find the similarity between the graphs.
It is an important tool in the fields like computer vision and pattern
recognition. Matching has applications in flow networks, scheduling
and planning, modeling bonds in chemistry, graph coloring, the stable
marriage problem, neural networks in artificial intelligence and more.
In image recognition applications, the results of image segmentation
in image processing typically produces data graphs with number of
vertices much larger than in the model graphs data expected to match
against. Perfect Matching theory is also known as graph isomorphism
problem. Many graph matching algorithm exist in order to optimize
for the parameters.
First we have to go through some definitions.
Definition 1. Matching in Graph: Am a t c h i n gi ng r a p hGi sa
setM={e1,e2,e3,···,ek}of edges such that each vertex v2V(G)
appears in at most one edge of M i.e ei\ej=, for all i, j.
The size of matching is the number of edges that appears in the match-
ing.
70munotes.in

Page 71

Definition 2. M- Saturated vertex : A vertex v is called as M-
saturated if for some e={xy},e2M.
If x is not saturated then it is unsaturated. 2 |M|=number of M-
saturated vertices.
Definition 3. Perfect Matching : A perfect matching in a graph G is
a matching in which every vertex of G appears exactly once, i.e Which
saturates every vertex or a matching of size exactlyn
2.
Definition 4. Maximum Matching : A matching m is called maxi-
mum if no other matching in G has a larger size.
Definition 5. Maximal Matching : A matching m is called maximal
ifM[{e}is not a matching for any e2E(G).
Definition 6. M- alternating Path :L e t M b e a m a t c h i n g i n a g r a p h
G . A path P in G is said to be M-alternating if every other edge in P
appear in M.
Definition 7. M- augmenting Path : An M-augmenting path is an
M-alternating path P={v1,v2,v3,···,vk}such that both v1,vkare
not vertices in M.
Theorem 5.1.1. Berg theorem : Let M be matching in a graph G
Then M is a maximum matching if and only if there does not exist any
M- augmenting path in G.
Proof. Suppose that M is a matching in G, such that there exist an
M-augmenting path say P. Notice that P must have odd length. Since
its edges alternate between edges in M and edges in G\M, and further
both begins and ends with edges from G\M. Let M0be the set of
edges in P that are not in M. Then notice that |M0|>|M|andM0
is a matching in G. so M is not a maximum matching. Hence if M is a
maximum matching, there can not be any M-augmenting path in G.
Conversely assume that M is a matching having no M-augmented path
in G. Let M2be a maximum matching in G. Note that by above argu-
ment , there is no M2augmenting path in G.
Let H be the sub graph of G having E(H)={e2Mb u te/ 2M2}[{e2
M2but e / 2M}. Let us consider the possible components of H. Note
that every vertex has degree 0, 1, or 2 in H. Vertices of degree 0 are
disregarded as their components are trivial. If a component has all ver-
tices of degree 2. It must be an even cycle alternating between edges
of M and edges of M2. If a components has a vertex degree 1 it must
be a path, alternating between edges of M and edges of M2. Note that
neither M nor M2has an augmented path G, we must have that such a
components begins with an edge from one matching and ends with an
edge from other matching.
In either cases every non trivial component of H has exactly half of its
71munotes.in

Page 72

edges from M and exactly half of its edges from M2. Hence we must
have that |M\M2|=|M2\M|. Hence
|M|=|M\M2|+|M\M2|=|M\M2|+|M2\M|=|M2|.
and thus M is also a maximum matching in G.
5.2 MATCHING IN BIPARTITE
GRAPHS
Let G be a graph with vertex set partitioned into two subsets A and
B such that every edges in G has one end points in A and the other in
B. Such graph is called as Bipartite graph. We will use the notation
G(A, B) for bipartite graph.
Suppose that A and B are subsets of G. We can say that A can match
with B if there exist a Matching M={e1,e2,e3,···,ek}such that each
eihas one vertex in A and the other in B and every vertex in A and B
appears in the matching.
5.2.1 Neighbour set of S in Graph G:
N(v) ={u2V(G)|u is adjacent to v }is called as the set of neighbour
of v.
Given a set S⇢V(G), we write N(S) =[v2SN(v)i st h es e to fv e r t i c e s
that are adjacent to atleast one vertex in S.
Theorem 5.2.1. Hall’s Theorem Let G(A, B) be a bipartite graph.
Suppose that |A||B|. Then there exists a matching M of size |A|
in G if and only if for every subset S⇢A, we have that |N(S)||S|.
In particular, If |A|=|B|, then G has a perfect matching under this
condition.
Proof. LetA={u1,u2,···,uk}andB={v1,v2,···,vl}with kl.
First suppose that there exist a matching M of size |A|in G. Since
G is bipartite, every edges of M includes one vertex of A. By possible
relabeling of B, suppose that M={e1,e2,···,ek}where ei={ui,vi}
for each i.
LetS⇢Awith S={us1,us2,···,ust}. Then vsj2N(S)f o ra l l
1jt. and hence |N(S)|t=|S|.
Converse we prove by induction on |A|. First , note that if |A|=1 ,
the theorem is trivial.
Let us assume that the theorem holds for |A|=k1.
Let G(A, B) be a bipartite graph with |A|=ksatisfying Hall’s condi-
tion. we consider two cases.
72munotes.in

Page 73

Case 1 For every proper subset S of A, |N(S)||S|+1.
Consider u1, without loss of generality suppose that u1is adjacent
tov1(and possibly some other vertices also). Consider the subgraph
Ho fGo n A\{u1},B\{v1}, i.e remove both vertices u1andv1from
consideration. Let S be a subset of A\{u1}. Then note that NH(S)i s
either equal to NG(S)o rh a sb e e nr e d u c e di ns i z eb y1d u et or e m o v a l
ofv1. In either case, |NH(S)||NG(S)|1|S|. And hence H
satisfies Hall’s condition. We can therefore obtain a matching in H of
size|A|1 by the induction hypothesis. adding the edge {u1,v1}to
such a matching produces a matching in G of size |A|.
Case 2 : A contains a proper subset S having |S|=|N(S)|.
Note that since S is a proper subset of A, by induction hypothesis
we have that the subgraph of G on (S, N(S)) satisfies Hall’s condition
and hence we may find a matching on this subgraph of size |S|. Let H
be the subgraph of G on ( A\S, B\N(S)): Note that we have removed
the same number of vertices from both A and B.
Let T be a subset of A\S. Then notice that NG(S[T)=NG(S)[
NH(T) and these two neighborhoods are disjoint. Furthermore by Hall’s
condition we have |NG(S[T)||S[T|=|S|+|T|.
Therefore |NH(T)|=|NG(S[T)||NG(S)||S|+|T||
S|=|T|.and hence H satisfies Hall’s condition. We thus can find a
matching in H of size |A\S|. Taking the union of this matching with
the matching on S gives a matching in G of size |A|as desired.
Some obvious features of perfect Matching:
(1) If G has an odd number of vertices, then it has no perfect matching.
(2) If G has any isolated vertices then it has no perfect matching.
(3) If G has a component of odd size, then it has no perfect matching.
Notation : For any given graph G, o(G)d e n o t et h en u m b e ro fo d d
components of G.
Theorem 5.2.2. Tutte’s Theorem : Let G be a graph . Then G
contains a perfect matching if and only if for every proper subset S⇢
V(G)we have o(G\S)|S|.
Proof. We first consider the forward implication. Suppose that G con-
tains a perfect matching M. Let S={v1,v2,···,vk}⇢V(G)b ea
proper subset of V(G). let G1,G2,···,Gnbe the odd components of
G\S. Since Giis odd, some vertex uiofGimust be matched under
Mw i t hav e r t e x viof S.
),o(G\S)=n|S|
73munotes.in

Page 74

Let us now consider the backward implication. Let G be a graph
on n vertices. We shall prove this by induction on n. Note the base
case is when n=2. Then G is K2. It satisfies Tutte’s condition and has
a perfect matching. Thus theorem hold for n=2.
We assume that if graph has n-2 or fewer vertices (note , we may delete
two vertices since no odd graph has a perfect matching and hence n is
even.) then the theorem holds.
Now we have a graph G on n vertices in which Tutte’s condition is
satisfied. We consider two case:
case 1: For every proper subset S of V(G), O(G\S)|S|1.
Note that as n is even, we must have that o(G\S)a n d |S|are of
the same parity. so infact we have o(G\S)|S|2f o re v e r yp r o p e r
subset of V(G).
Fix an edge uv and consider H=G\{u, v}having n-2 vertices. Let
T⇢V(H). Note that o(H\T)=O(G\(T[{u, v}))|t[{u, v}|
2=|T|. Hence H satisfies tutte’s criterion and thus H has a perfect
matching M0. Taking M=M0[{uv}yields a perfect matching in G.
case 2: There exist a proper subset S of V(G) with o(G\S)=|S|.
Let S be the largest proper subset of V(G)h a v i n g o(G\S)=|S|=k
and let S={v1,v2,···,vk}. We first claim that G\Scontains only
odd components. Let if H be an even component of G\S. Then
fix any vertex u02V(H). Note that H\{u0}must have atleast
one odd component as it has an odd number of vertices and hence
|S[{u0}|o(G\(S[{u0}))|S[{u0}|.yielding a strictly larger
set satisfying the hypothesis of the case. Hence no even component
exist.
LetG1,G2,···,Gkbe the k-components of G\Sand each of these is
odd. Create a bipartite graph B as follows.
Let V=S and let U={u1,u2,···,uk}. Put an edges uivjin B if vj
is adjacent to some vertex in Gi.
Claim: B satisfies Hall’s criterion.
Suppose T is a proper subset of U with |T|=t. Suppose that
|N(T)|<|T|. Let S0={vi1,vi2,···,vir}=N(T)⇢S, with
rnent of G\S0. since it is adjacent to no other vertices in S. Hence
o(G\S0)t>r =|S0|. This is a contradiction of Tutte’s condition.
Hence B satisfies Hall’s criterion.
Therefore , there exist a perfect matching M in B. Without loss of gen-
erality by relabel the components of G\Sso that we have, for every
vi2S. That viis adjacent to some vertex of Gicall this vertex as ui.
Let us first show that we can find a perfect matching in Gj\ujfor all
74munotes.in

Page 75

j. If|V(Gj)|= 1 then we are done. if not , suppose that |V(Gj)|3.
LetH=Gj\{uj}. Let W⇢V(H) be a proper subset. Note that
O(H\W)=o(G\(S[{uj}[W))(k1). Since we have all the odd
components G1,G2,···,Gk. Excepting Gjcounted in the right hand
side, which can be rectified by simply subtracting k-1. Moreover due
to maximality of S. We have o(G\(S[{uj}[W))<|S[{uj}[W|=|
W|+k+1 and hence o(H\W)<|W|+k+1(k1) =|W|+2. As
o(H\W)a n d |W|must have same parity. This implies o(H\W)|
W|. Hence H satisfies Tutte’s criterian. Thus by induction we can
form a perfect matching in H.
By performing the above procedure. We thus can form a perfect
matching MjinGj\{uj}for all j. Taking M1[M2[···[Mj[
{u1v1,u2v2,···,ukvk}yields a perfect matching in G.
5.3 Independent sets and covering
Definition 8. Independent set(Stable set) : Let G(V, E) be a
graph. A independent set is a subset C of V such that no two ver-
tices of C are adjacent in G.
An independent set is maximum if G has no independent set C’ with
|C0|>|C|.
Definition 9. Vertex cover: A vertex cover is a set W of V such that
every edge of G has atleast one end in W.
Definition 10. Edge cover: A edge cover is a subset F of E such that
for each vertex v there exist e2Fsatisfying v2e.
Note: An edge cover can exist only if G has no isolated vertices.
Notation:
↵(G)=max{|C|/ C is a independent set. }
⌧(G)=min{|W|/ W is a vertex cover }
v(G)=max{|M|/ M is a Matching }
⇢(G)=min{|F|/ F is an edge cover }
Note: ↵(G)⇢(G)a n d v(G)⌧(G)
Theorem 5.3.1. A set C⇢Vis an independent set of G if and only
ifV\Cis a vertex covering of G.
75munotes.in

Page 76

Proof. By definition , C is an independent set of G if and only if no
edge of G has both ends in Cor equivalently if and only if each edge
has atleast one end in V\C. But this is so if and only if V\Cis a
vertex covering of G.
Corollary 5.3.1. ↵(G)+⌧(G)=n.
Proof. Let C be a maximum independent set of G and W be a minimum
vertex covering of G. Then by above theorem V\Wis an independent
set and V\Cis a vertex covering.
Therefore n⌧(G)=|V\W|↵(G)···(1).
n↵(G)=|V\C|⌧(G)···(2).
From (1) and (2) we have ↵(G)+⌧(G)=n.
Theorem 5.3.2. (Gallai’s theorem) : If G=(V, E) is a graph with-
out isolated vertices then v(G)+⇢(G)=|V|.
Proof. Let M be a matching of size v(G). Let U be the set of M- un-
saturated vertices (vertices which are not end point of any edge in M).
Since G has no isolated vertex and M is maximum, there exist a set E’
of|U|edges, one incident with each vertex in U. Clearly, M[E0is
an edge covering of G, and so
⇢(G)|M[E0|=v(G)+(n2v(G)) = nv(G)
⇢(G)+v(G)n···(1)
Now let L be a minimum edge covering of G, set H=G[L] and let M be
a maximum matching in H. Denote the set of M-unsaturated vertices
in H by U. Since M is maximum, H[U] has no links and therefore
|L|v(G)=|L\M||U|=n2v(G)
|L|+|M|n
Because H is a subgraph of G, M is a matching in G and so
⇢(G)+v(G)|L|+|M|n
⇢(G)+v(G)n···(2)
from (1) and (2) we get
⇢(G)+v(G)=n
Let M be a matching and K be a covering such that |M|=|K|
then, M is a maximum matching and K is a minimum covering.
Proof. If M’ is a maximum matching and K’ is minimum covering then
|M||M0||K0||K|
Since |M|=|K|, it follows that |M|=|M0|and|K|=|K0|.
76munotes.in

Page 77

Theorem 5.3.3. Koings matching Theorem : In a bipartite graph,
the number of edges in a maximum matching is equal to the number of
vertices in a minimum covering.
Proof. Let G be a bipartite graph with bipartition (X, Y) and let M’ be
am a x i m u mm a t c h i n go fG .L e tUb et h es e to fM ’ -u n s a t u r a t e dv e r t i c e s
in X and Let Z be the set of all vertices connected by M’-alternating
paths to vertices of U. Let set S=Z\XandT=Z\Y.
Then by Hall’s theorem, we have that every vertex in T is M’-saturated
and N(S)=T. Define K0=(X\S)[T. Every edge of G must have
atleast one of its ends in K’ or otherwise, there would be an edge with
one end in S and one end in Y\T, contradicting N(S)=T. Thus K’ is
ac o v e r i n go fGa n dC l e a r l y |M0|=|K0|. By above lemma K’ is a
minimum covering. The theorem follows.
Theorem 5.3.4. Konigs’s edge covering theorem : In a bipartite
graph G with no isolated vertex, the number of vertices in a maximum
independent set is equal to the number of edge in a minimum edge
covering.
Proof. let G be a bipartite graph with no isolated vertex, By Gallai’s
theorem, we have ↵(G)+⌧(G)=v(G)+⇢(G)a n ds i n c eGi sb i p a r t i t e,
it follows from Konig’s matching theorem v(G)=⌧(G). Thus ↵(G)=
⇢(G).
5.4 The Personnel Assignment problem:
In a certain company , n workers X1,X2,···,Xnare available
for n jobs y1,y2,···,yn, each worker being qualified for one or more
of these jobs. Can all the men be assigned, one man per job, two jobs
for which they are qualified? This is the personnel assignment problem.
We construct a bipartite graph G with bipartition (X, Y), where
X={x1,x2,···,xn},Y={y1,y2,···,yn}andxiis joined to yjif
and only if worker xiis qualified for job yj. The problem becomes one
of determining whether or not G has a perfect matching. According to
Hall’s theorem either G has such a matching or there is a subset S of
X such that |N(S)|<|S|. Now we present an algorithm to solve the
personnel assignment problem.
Algorithm: Start with an arbitrary matching M.
(1) If M saturates every vertex in X then stop otherwise, Let u be
an M-unsaturated vertex in X. Set S={u}andT=.
77munotes.in

Page 78

(2) If N(S)=T then |N(S)<|S, Since |T|=|S|1t h e ns t o p .s i n c e
by Hall’s theorem there is no matching that saturates every vertex in
X. Otherwise , let y2N(S)\T.
(3) If y is M-saturated, let yz2M. Replace S by S[{z}and T
byT[{y}and go to step2. (observe that |T|=|S|1 is maintained
after this replacement.) Otherwise, let P be an M-augmenting (u-y)
path. Replace M by M0=ME(P)a n dg ot os t e p1 .
Consider a graph given below with initial matching M={x2y2,x3y3,x5y5}.
assignment 1.jpg
An M-alternating tree is grown, starting with x1and the M-augmenting
path x1y2x2y1found. as shown in figure below.
This result in a new matching M0={x1y2,x2y1,x3y3,x5y5}
as shown in figure below.
An M’-alternating tree is now grown from x4. Since there is no M’-
augmenting path with origin x4, the algorithm terminates.
78munotes.in

Page 79

The set S={x1,x3,x4}with neighbour set N(S)={y2,y3}shows that
G has no perfect matching.
Flow Chart of Hungarian Method:
5.5 Ramsey Number
Definition 11. Clique: A clique of a simple graph G is a subset S of
79munotes.in

Page 80

V(G) such that any two vertices of S are adjacent.
S is a clique of G if and only if S is an independent set of Gc.
If G has no large cliques, then G has a large independent set.
The above remark was first proved by Ramsey (1930).
Question:
Among 6 people , there are either 3 who know each other or 3 who
do not know each other.
Proof: Let 1,2,3,4,5,6 be the 6 people. Consider these 6 people as ver-
tices of graph. i vertex is connected to j vertex by an edge then it means
i and j know each other. otherwise they do not know each other. Let
us select vertex 1 and join the with some of remaining vertices. By pi-
genhole principle, either 1 knows 3 people or 1 does not know 3 people
i.e 1 is connected to either 3 vertices or not connected to 3 vertices by
an edge.
Case1: If 1 is adjacent to three vertices .
If 1 is adjacent to three vertices say a, b, c. If two of a, b, c are adjacent
then 1 with those two vertices form K3. This means 1 and other two
people know each other.
Otherwise if none of a, b, c are adjacent. Then we get three isolated
vertices, i.e we get three people they do not know each other.
Case2: 1 is not adjacent to three vertices.
If 1 is not adjacent to three vertices a, b, c. If two of a, b, c are not
adjacent then we get three vertices isolated. means Three people do
not know each other.
Definition 12. If we color the edges of Knwith red or blue, then there
is ethier a set of r vertices such that edges among them are colored red
or a set of b vertices such that edges among them are colored blue.
Definition 13. Ramsey Numbers: For any positive integers k and
l2t h e r ee x i s tas m a l l e s ti n t e g e rt = r ( k ,l )s u c ht h a ta n yg r a p ho nt
vertices contains either a clique of k vertices or an independent set of l
vertices.
r(1,l)=r(k,1)=1
r(2, l)=l, r(k, 2)=k, r(k, l)=r(l, k)
Theorem 5.5.1. For any two integers k2and l2then prove
that r(k,l)r(k,l1) + r(k1,l). Furthermore, if r(k,l1)and
r(k1,l)are both even, then strict inequality holds .
Proof. Let G be a graph on r(k,l1) + r(k1,l)v e r t i c e s ,a n dl e t
v2V. We distinguish two cases:
80munotes.in

Page 81

Case1: vi sn o na d j a c e n tt oas e to fa t l e a s t r(k,l1) vertices.
G[S] contains either a clique of k vertices or an independent set of l1
vertices and therefore G[S[{v}] contains either a clique of k vertices
or an independent set of l vertices.
Case2: vis adjacent to a set T of atleast r(k1,l)v e r t i c e s .
G[T] contains either a clique of k-1 vertices or an independent ser of l
vertices.
Therefore G[T[{v}] contains either a cilque of k vertices of an inde-
pendent set of l vertices.
Since one of case(1) and case(2) must hold because the number of ver-
tices to which v is non adjacent plus the number of vertices to which v
is adjacent is equal to r(k,l1) + r(k1,l)1.
Proof. Thus r(k,l)r(k,l1) + r(k1,l)
Now suppose that r(k, l-1) and r(k-1, l) are both even and let G be
ag r a p ho n r(k,l1) + r(k1,l)1v e r t i c e s . S i n c eGh a sa no d d
number of vertices, then some vertices v is of even degree; in particular
, v cannot be adjacent to precisely r(k1,l)1 vertices. Consequently,
either case1 or case2 of above holds and therefore G contains either a
clique of k vertices or an independent set of l vertices.
Thus r(k,l)r(k,l1) + r(k1,l)1a ss t a t e d .
Theorem 5.5.2. Prove that r(3,3) = 6 ,r(3,4) = 9 ,r(3,5) = 14 ,
r(4,4) = 18 .
Proof. (1): From Theorem above we can get, r(3,3)r(3,2)+r(2,3) =
3+3=6 ···(1)
From figure below , The 5 cycle contains no clique of three vertices and
no independent set of three vertices.
It shows that r(3,3)6···(2).
from (1) and (2) r(3,3) = 6
Proof. (ii) From Theorem above we can get, r(3,4)r(3,3)+r(2,4)
1=6+4 1=9 ···(1)
81munotes.in

Page 82

The graph of figure below , contains no clique of three vertices and no
independent set of four vertices.
It shows that r(3,4)9···(2).
from (1) and (2)
r(3,4) = 9
Proof. (iii) From Theorem above we can get
r(3,5)r(3,4) + r(2,5) = 9 + 5 = 14 ···(1)
The graph of figure below , contains no clique of three vertices and no
independent set of five vertices.
It shows that r(3,5)14···(2).
from (1) and (2)
r(3,5) = 14
Proof. (iv) From Theorem above we can get
r(4,4)r(4,3) + r(3,4) = 9 + 9 = 18 ···(1)
The graph of figure below , contains no clique of four vertices and no
independent set of four vertices.
82munotes.in

Page 83

It shows that r(4,4)18···(2).
from (1) and (2)
r(4,4) = 18
Definition 14. Ramsey graph :A (k, l)- Ramsey graph is a graph on
r(k,l)1v e r t i c e st h a tc o n t a i n sn e i t h e rac l i q u eo fkv e r t i c e sn o ra n
independent set of l vertices.
Such a graph exist for all k2a n d l2. All the graph shown in the
above theorem represent Ramsey- graph.
Theorem 5.5.3. r(k,l)k+l2
k1
.
Proof. We will prove this by induction on k, l. First consider the base
case as k=l=2. r(2,2) = 2 2+22
21
.
Now assume the relation holds for all k=x-1, l=y and k=x , l=y-1 cases.
We now prove result holds for k=x, l=y.
By using above theorem and Pascal’s rule
r(k,l)r(k1,l)+r(k,l1)(k1)+l2
(k1)1
+k+(l1)2
k1
=k+l2
k1
r(k,l)k+l2
k1
Theorem 5.5.4. Prove that r(k,k)2k
2.
Proof. Since r(1,1) = 1 and r(2,2) = 2, we may assume that k3.
LetSnthe set of simple graphs with vertex set {v1,v2,···,vn}andSnk
the set of those graphs in Snthat have a clique of k vertices.
As each subset of then
2
possible edges vivjdetermines a graph in Sn.
Therefore, |Sn|=2(n
2)···(1)
Similarly, the number of graphs in Snhaving a particular set of k ver-
tices as a clique is 2(n
2)(k
2).Since there aren
k
distinct k-elements sub-
sets of {v1,v2,v3,···,vn}. we have,
|Snk|n
k
.2(n
2)(k
2)···(2)
Dividing (2) by (1) we get,
|Snk|
|Sn|n
k
.2(k
2)2)
k!
Proof. Suppose , now that n<2k
2
|Snk|
|Sn|2k2
2.2(n
2)
k!=2k
2
k!<1
2
83munotes.in

Page 84

Therefore, fewrer than half of the graph in Sncontains a clique of k-
vertices. Also, fewer than half of the graphs in Sncontains an inde-
pendent set of k - vertices. Hence some graph in Sncontains neither a
clique of k- vertices nor an independent set of k vertices. Because this
holds for any n<2k
2, we have r(k,k)2k
2
Corollary 5.5.1. Ifm=min{k,l}, then r(k,l)2m
2.
Theorem 5.5.5. r(k1,k2,···,km)r(k11,k2,···,km)+r(k1,k2
1,···,km)+···+r(k1,k2,···,km1)m+2
Theorem 5.5.6. r(k1+1,k2+2,···,km+1 ) (k1+k2+···+km)!
k1!.k2!.k3!.....k m!
5.6 Chapter End Exercise
1. Show that every k-cube has a perfect matching ( k2).
2. Find the number of di ↵erent perfect matchings in K2nandKn,n.
3. Show that a tree has at most one perfect matching.
4. Deduce Hall’s theorem from Konig’s theorem.
5. Derive Hall’s theorem from Tutte’s theorem.
6. Show that a tree G has a perfect matching if and only if o(G\v)=
1f o ra l l v2V.
7. Describe how the Hungarian method can be used to find a maxi-
mum matching in a bipartite graph.
8. Show that G is bipartite if and only if ↵(H)1
2v(H)f o re v e r y
subgraph H of G.
9. Show that G is bipartite if and only if ↵(H)=⇢(H)f o re v e r y
subgraph H of G such that (H)>0.
10. Show that, for all k and l, r(k,l)=r(l,k).
11. Let rndenote the Ramsey number r(k1,k2,···,kn)w i t h ki=3
for all i. (a) Show that rnn(rn11) + 2 .(b) Noting that
r2=6 ,u s e( a )t os h o wt h a t rn[n!e] + 1. (c) Deduce that
r317.
12. Deduce that r(2n+1,2n+1 ) 5n+1f o ra l l n0.
84munotes.in