Isometric cycles, cutsets, and crowning of bridged graphs

Abstract A graph G is bridged if every cycle C of length at least 4 has vertices x , y such that d G ( x , y ) < d C ( x , y ). A cycle C is isometric if d G ( x , y ) = d C ( x , y ) for all x , y ∈ V ( C ). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g . We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G [ S ] = H . This provides counterexamples to Hahn's conjecture that d G ( u , v ) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G . We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003