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?
2
-
1$\begingroup$ Hint for b: o-o $\endgroup$– Hagen von EitzenOct 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$– Cameron BuieOct 23, 2013 at 18:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Oct 23, 2013 at 17:52