Data Structures, Algorithms, & Applications in C++
Chapter 16, Exercise 13
We shall show that for every pair (u,v) of distinct vertices
in V, there exists a
u
to v path in
G that does not use the
edge (i,j). Hence, this path is
also present in H =
(V,
E -
{(i,j)} and so
H is connected.
Let u and
v be two arbitrary but distinct vertices in
V. Since
G is connected,
G contains a
u
to v path,
P.
Let x be the number
of times P uses the edge
(i,j) in the direction
i to
j. Let
y be the number of times this edge is used in the direction
j to
i. Observe that
x =
y = 0 iff
P does not use this edge. Since,
(i,j) is on a cycle of
G, there exists a simple path
C of the form:
C =
i, j, i1, i2, ..., ik , i
A u to
v path that does not use the edge
(i,j) may be obtained
from P as follows:
- (a)
-
Replace each use of the edge
(i,j) in the direction
i to
j by the path
i,
ik, ..., i2, i1, j.
- (b)
-
Replace each use of the edge
(i,j) in the direction
j
to i
by the path j,
i1, i2, ..., ik, i.
Hence, G contains a
u to
v path that does not use the edge
(i,j). This path is therefore a
u to
v path in
H. So,
H is
connected.