1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Hint for b: o-o $\endgroup$ – Hagen von Eitzen Oct 23 '13 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$ – Cameron Buie Oct 23 '13 at 18:17
5
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.