[Math] Prove that if a graph contains a bridge, it is not Hamiltonian. Can it contain an Hamiltonian path

graph theory

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?

Best Answer

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.