Draks asked a question about a sentence in Wikipedia stating that such-and-such (NP-hardness of Hamiltonian path detection) is true for "bridgeless undirected planar 3-regular bipartite graphs". What does "bridgeless" mean in this context? It seems to me that it is implied by the other properties, at least if they mean what I'm used to meaning:

  • "Bridgeless": The graph has no cut of size one. That is, if you remove any edge, its two endpoints are still connected by a path.
  • "3-regular": Every vertex is an endpoint of exactly three edges.
  • "Bipartite": The graph can be 2-vertex-colored.

With these meanings, it is impossible for a $k$-regular ($k\ge 2$) bipartite graph to contain a bridge. Namely, if there is a bridge, consider the the number of edges in one of the parts it falls into upon removing the bridge. This must be both $k-1$ and $0$ modulo $k$, as can be seen by counting first vertices of the same color as the bridgehead and then those of the opposite color.

Does "bridgeless" mean something different in this context, then?

My initial speculation was that it might be special Hamiltonian-jargon for "3-edge-connected", but it is not clear to me how that is effectively different from "3-(vertex)-connected" in the presence of the other restrictions.

  • $\begingroup$ Perhaps: xkcd.com/386 $\endgroup$ – Chris Godsil Feb 8 '13 at 20:06
  • $\begingroup$ @Chris: Possibly, but I try not to make that my first assumption. $\endgroup$ – Henning Makholm Feb 8 '13 at 21:20
  • 1
    $\begingroup$ Very reasonable. But in this context I have only ever seen bridge used with the meaning "cut edge". $\endgroup$ – Chris Godsil Feb 8 '13 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.