Bonds of a Graph G and it's related statements

307 Views Asked by At

I am referring Diestel's book on Graph Theory 5th Edition.

Lemma 3.1.3. The following statements are equivalent for distinct edges e, f of a graph G:

(i) The edges e, f belong to a common block of G.

(ii) The edges e, f belong to a common cycle in G.

(iii) The edges e, f belong to a common bond of G.

In the explanation of above lemma, they give the following:

(ii)→(iii) Deleting e and f from a cycle C $\ni$ e, f leaves a partition of V (C) into two connected sets. Extend this to a partitition into two connected sets of the vertex set of the component of G containing C. The edges between these sets form a bond of G containing e and f.

How can we proove the statement (iii) from the assumption (ii)? How the above explanation helpful for proving this?

2

There are 2 best solutions below

1
On

Deleting an edge from a cycle produces a path. Deleting a second edge from the cycle disconnects the cycle into two components. We let $S$ be the vertex set of one component, and $\overline{S}$ be the vertex set of the other.

A bond is a minimum edge cut, which is the smallest number of edges to disconnect vertex sets $S$ and $\overline{S}$. In the case of a cycle, a bond just so happens to be two edges.

1
On

Let the common bond be $[S,\overline{S}]$, then $G[S], G[\overline{S}]$ are all connected (referring Theorem 2.15 in Bondy's book Graph Theory) such that there exist two paths connecting two ends of $e$ and $f$, forming a cycle which is what we need.