Sebanyak 1 item atau buku ditemukan

Engineering Mathematics – Volume Ii

An edge e of G is a bridge ofG if and only ife does not lie on any cycle of G. Proof.
Let e be a bridge of G. Suppose u, v are the end vertices of e and e does lie on a
cycle, say C : u, v,w, . . . , x, u. The graph G — e contains a u—v path say u, x, . . . ,
w, v and hence u is connected to v. We have to prove that G — e is connected.
Let x and y be any two vertices of G — e. To prove G — e contains an x-y path.
Since G is connected, there is an x-y path P in G. Now, there are two possibilities:
e ...