A bridge in a connected graph G is an edge whose deletion disconnects the graph. (Only the edge is deleted | not the vertices.) Prove that if a graph contains a bridge, it is not Hamiltonian. Can it contain a Hamilton path?

  • 1
    $\begingroup$ Hint for b: o-o $\endgroup$ Oct 23, 2013 at 17:53
  • $\begingroup$ What are your thoughts and efforts on the problem thus far? The more you can tell us, the more easily we can tailor answers to your needs. $\endgroup$ Oct 23, 2013 at 18:17

1 Answer 1


HINT: Let $C_0$ and $C_1$ be the two components that remain when you delete the bridge. If there’s a Hamilton circuit, start traversing it at any vertex in $C_0$; at some point you must cross the bridge. Now how are you going to return to the starting point?

I’m sure that you can find a graph that has both a bridge and a Hamilton path.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .