6-34 5.
DISCRETE MATHEMA
(ut Edge. Cut cdge ina graph is an cdgc whose removal results n a disconnected graph
For example,
In above graph edge e is cut edge.
Region. Aplane graph partitions the plane into several areas. These areas are caled regions
faces. Each region is depected by the set of edges.
Degree of aFace. IfG be a graph and g be its face then the number of edges in the boundary o
with cut cdges counting twice is degree of th¹
Jertey
For example.
Various regions are R R, R;
deg (R,)=3, deg (R,) =3, deg (R,) =4
6.10.1 Euler's Formula
LetG=(V, E) be a connected planar graph and let Rbe the number of
planar depiction of Gthen R=IEl -IVI+2 rrgions defined by ar
Proof. We prove that result by induction. Let nbe the no. of regions
determined by G.
For n= ,the result is true for n= 1,
For example,
Here.
R= 1, El= 1,V|=2
6
sRAPHTHEORY
IE)-IVI+2 =1-2+2 =1=R
and
R=|E |V| +2
Also
Vertces
R= KtI egrom
R=1, El = 2, IV| = 3 L - delele
=2-3+ 2=1=R
R' R
n=1
.result is true for
is true for n=k>1.
Let us assume, that result
for n=k+1
To prove. result is true is Common to
determining k + 1 regions. Remove an edge which
graph
Let Gbe a connected planar graph Ghaving k-regions.
two regions. We obtain a G, then
te boundary of vertices, no. of edges and no. of regions of
respectively the number of
Let |V", IEI, R' denote
R'=IE1-IV1+2
0V|=IVI, IE|= IEI 1, R'= R- 1
. We have
+1-[V|+2
IEIIVI +2= |E|
= (E| -IVI+2) + 1
=R+1
=R
.result is true fork+ 1.
connected graphs.
result is true for all graph with more than one edge,
nence by induction, connected Planar
E) be asimple,
6.10.2 Theorem, Let G= (V.
hen the following inequalities holds :
(i) 2IE| >3R
ü) IEl< 3IVI 6
suchthat
deg(v) s5
(iüü) There is a vertex y of G (the unboundedIregion), then
R= 1 &
one region
defines only
Proof.() We: assume that |El >1, IfG
) certainly holds. IEl> 1
IR0 =l&
[:2E23 IRI,
i.e. IEl>2,
Clearly 2 IEI
2 3]
6-36 DISCRETE MATHEMATICS
Now if RI > 1, then cach region is bounded by at least 3cdges. But each edge in a planar graplh
TOuches at most 2 regions. Thus, we have 2 \El > 3IKI.
(ii) By part (i), 2 |El S3 IRI
Or IRIsIEI, Add| Vlon both sides
3
IVI+IRISIVi+IEI
By Euler's Formula 6.10.1
IVI-IE|+IR| =2
IV|+RI= |El +2
Put in (1), IEl +2 SE+ 3
Multiplying by 3,
3 IBI + 6<3IVI +2 IEI
IEI< 3IV|-6
Example 22. Prove that every planar graph has at least one vertex of degree 5 or less than 5.
Sol. Let G be a graph having all vertices of degree 6 or more. Then the sum of the degrees of all the
vertices would be greater than or equal to 6.
but the sum of the degrees of the vertices is twice the number of edges,
.:. we have 6v < 2e
Vsel3
..)
But by property of planar graph, rs 2e
3
ByEuler's formula, 2=y-e+r ...i)
2e
.. From (), (i) and (ii), 2s-e+
3 3
=0
which is not true.
. There must exist some vertex in G with
degree 5 or less than 5
610.3 Non-Planar Graph. Agraph is
non-planar if it cannot be drawn in a plane so that
cross. The following graphs is a non-panar graph. n0 ev
6-37
23,
the graph kz is non planar.
Prove that
Aample
Number of vertices in k= |V|=5
Number of edges in k<= El= 10
planar graph, then |El S3 IV|6
IfGisa
10 < 3:5 -6
contradiction.
10<9, which is a
ie.
graph.
k7is non planar
CIRCUITS
Eu EP PATHS AND theory. This paper developed
marked the birth of graph
Euler's 1736 paper which
problem, which is the following.
We have mentioned Konigsberg. Bridge
the so-called
are two islands in the river,
to solve There
ory, which was able the town of
Konigsbergin Russia.
problem for the
citizens of
through Figure. The
flows shown in took in every
IhePregel River each other by bridges as the banks or islands, which
walk; the
and beginning on one
of find such a
URCted to the banks was a walk, They were unable to
whether there starting'position.
Mgsoerg was back at the ...???.
and finished that none
islands and seven
bridges
gCkactly once a walk or to show
included two through
lem was either to find such of Konigsberg anywhere, can a person walk tothe
Russian town
East ending Konigsberg wrote
The eighteenth -century : Beginning anywhere andtwice '? The people of 1736 that such a walk
is
(a) Question any bridge in
n Fig. l. crossing
question. Euler
proved
bridges by curves,
but not point and the
all seven bridges Euler aboutthis river by
L. the
Pterated two sides of
Mathematician
Swiss islands and the
sible. He replaced the
hating Figure 1(b).
B
A
D
D
Soe. DISCRETE MATHEMATI
6-40
Here deg (a) =3, deg (b) =
=3, deg (c)=3and deg (b) =5 as the vertices have odd degree so there.i
no possibility of an Euler circuit.
6.11.1 Euler Path
Let Gbe a graph and let yand wbetwo vertices of G. An Euler path from vto wis a sequeNCe of
adjacent edges and vertices that starts at v, end and w, passes through every vertex of Gat least once, and
traverses every edge of Gexactly once.
Corollary. Let Gbe a graph and letvand wbetwo vertices of G. There is an Euler path from vtoy
if, and only if, Gis connected,,v and whave odd degree and all other vertices of Ghave even degree.
Exámple 24. Determine whether the following graph has Euler circuit.
2 Vehey ane C
Vevt cobe caucel a
Sol. From above clearly deg (a) =2, deg (b) =4, dec (c) =4dec (d) =4, deg (e) =2, deg () =4, de
(g) = 4, deg (h) = 4, deg () = 4
Since the degree of each vertex is even, and the graph has Euler Circuit, One such circuit is :
abcdefg dfi hcghbia
Example 25. Determine whether the following graph has an Euler circuit.
V3
VA
V
8cDBAD
B<DABD
Vor
ABCoEBED A
Vg
Vg
Sol. Asdeg (v;)=5, an odd degree so the given graph has not an Euler circuit.
6.11,2. Theorem : Prove that an undirected graph Gpossesses a Eulerian circut iff it
and all its vertices are of even degree.
is connec
(P.TU., B.Tech May 2003, Dec. 2003, Dec. 20
Soi. Let the undirected graph possess an Eulerian circuit
:. By definition, the graph must be connected.
C Now, since the graph has Eulerian circuit
LE . Every time the graph meets a vertex, it goes the vertex al-
BCAB
have not been traced before. through edges which are incidnt vwith
DE DE BcABpc £fD
Thus. the degree of every vertex in a the graph
must be even.
612 HAMILTONIAN GRAPHS
seck l alngevy aige ot the graFh
An Eulenan path (once) andretumto the starting postuoT
weaNit vy veTter one, without travelling
um the starmng st lhis problem was along any edge mort
e. and considered by Hamilton (although he w2s
otthe tìrst with these paths.
The above àsusion of Eulenan graphs emhasized traveling
iv8 AHalmiltonian Cit maQraph G, named after the edges; here we concentrate on visiing
nineteenth-century Insh nmathematician
Hamilton 1803-1S5. S a clsed path that vìsits every vertex
in G exactly once. (Such a closed
h mist be acycie.) Ir Gdes ainmt a Hailtonian circuit, then Gis
called a Haniltonian graph. Note
ot an Eulerian circutaveES EeY ige exactly once, but may
repeat vertices, while a Hamiltonian
incit visits each vertex exaciy one but may epeat edges. Figure. lgives
an example of a graph which
&Hemiltonian but not Eulerian. and vice versa.
Fig. 1. (a) Hamiltonian and non-Eulerian (b) Eulerian and non-Hamiltonian
Although it isclear that only connected graphs can be Hamiltonian, there is no simple criterion to tell
as whether or not a graph is Hamiltonian as there is for Eulerian graphs. We do have the following
ufficient condition which is due to G. A. Dirac.
6.12.1. Theórem. ILet Gbe a connected graph withn vertices. Then Gis Hamiltonian if n>3 and ns
eg (v) for each vertexvin G. AJo
6.12.1. Hamiltonian Circuits : Given agraph G, aHamiltonain circuit for Gis asimple curcuit that
cludes every vertex of G. That is, aHamiltonian circuti for Gis a sequence of adjacent vertices and
istinct edges in which every vertex of Gappears exactly once.
A Hamilton cycle in a graph [digraph] is a cycle [directed cycle] that includes all vertices of the
raph.
Agraph or digraph is Hamiltonain if it contains aHamilton cycle.
AHamilton path in a graph [digraph] is a path [directed path] that includes all vertices of the grat
6.12.3. Proposition. If agraph Ghas aHamiltonian circuit then Ghas asub-graph H
with the illowg
Droperties :
1. H contains every vertex G
2. His connected.
3. H has the same number of edges as vertices
4. Every vertex of H has degree 2
the following conditions:
Aconnected graph is a Hamiltonainfor
6-46
DISCRETE MATHEMATICS
I. AHamiltonian graph bas no cut-point. (Thus, it is 2-connected.)
2. The previousfact has this generalization : Let Gbe a
Hamiltonain graph and letScVG.Then the
graph GS has at most ISlcomponents.
number of vertices in the two parts of the bipartition
. Bipartite Hamiltonian graphs have an equal
minimum degree at least n/2, then it is Hamiltonain
T a simple graph has n 3 vertices and
(Dirac, 1952).
the
every pair of nonadjacent vertices u and vsatisfies
D. lTasimple graph has n 3 vertices, and if
inequality deg (u) +deg () 2n, then it is Hamiltonian.
sequence d, Sa, s... sa, and th¡t
6. Suppose that a simple graph with n >3 vertices has degree Hamiltonan.
Tor every i with 1siS n2 either d,> ior d. ,2n-i. Then the graph is
(n'- 3n + 6)/2 edges is Hamiltonian.
7. Every simple graph with n >3 vertices and at least
is at least as large as its independence
8. Every graph with at least three vertices whose connectivity ()
number (oc) is a Hamiltionian graph.
9. Every 4-connected planar graph is Hamiltionain.
resulting digraph always
10. If the edges of the complete graph K, are assigned directions, then the
has Hamilton directed path.
cycles.
1. The edges of the complete graph Km+ 1Can be partitioned into nHamiltion
containing
12. A graph Gis non-Hamiltonian if there is a subset of mutually nonadjacent vertices
more than half the vertices of G.
on n
13. "Almost all" graphs are Hamiltionain. That is, of the exactly 2 - 1)2 simple graphs
(labeled) vertices, the proportion that are Hamiltionain tends to 1 as n ’ o,
no
14. SuppOse that a simple graph is constructed by the following process : start with n vertices and
edges; until the minimum degree is 2, apossible edge is chosen uniformly at random from among the edges
not already in the graph, and added to the graph. With probability tending to 1 as n ’ oo, the resulting
graph is Hamiltionain.
15. The following table tells which members of several infinte families of graphs are Hamiltonian.
Graph Hamiltonian ?
bouquet B,, for all n 21
dipole D, for all n 2
Complete graph K for all n 23
complete bipartite graph Km,n when m=n
cycle graphC, for all n 1
wheel W, for all n 2
hypercube Q, for all n 2
any tree if|V|= 1
GAAPH THEORY
Example 29. Show that the following graph does not have aHamiltonian cirucit.
Solution. Here deg (c) =5,if we remove 3edges from vertexcthendeg (b) <2, deg (g)<2or eg)
<2, deg (d) <2.Imeans that this graph does not satisify the desired properties as above, so the grapt oes
not have a Hamiltionian circuit.
Example. 30. Find Hamiltonian Cycle for the following graph.
R
DM/
V
RSTVWXHJKLMNPCDFGBZOR.
Solutiox. The Hamiltonian cycle for the given graph is :
Esample 31. Find Hamiltonian Circuit for the following graph.
a e
Solution. The HamiltonianCiruit for the given graph is : a bdefcgha
Another Hamiltonian Circuit for the given graph could be : abcdefgha
Example 32. Which ofthe following graphs have aHamiltonian cirucit ?If not, why not ?
(a) (b) (C
