Bridge in Hamilton graph

Question

My task is to prove that Hamilton graph does not contain bridges(that is edge, and by removing that edge graph is disconnected). It is kind of obvious that by removing any edge from Hamilton contour graph will stay connected, but not sure how to prove that in formal way. Any help is appreciated.

Answer 1

An argument by induction might work. Start with a very small Hamilton graph and induct on adding one node and sufficient edges that it remains Hamiltonian and removing an edge will cause that to break.

Answer 2

Proof by contradiction is a natural choice. Suppose $G$ is Hamiltonian and contains a bridge $(i,j)$. Let $C$ be a Hamiltonian cycle. Removing edge $(i,j)$ from $G$ leaves a path $C \setminus \{(i,j)\}$ that contains all nodes, so $G \setminus \{(i,j)\}$ is connected, contradicting the fact that $(i,j)$ is a bridge.

Answer 3

Here's a more formally-structured proof. Don't take this as a recommendation for how to structure your graph theory proofs! I prefer Rob Pratt's proof, even though it lacks some of the formality.

Suppose $G = (V, E)$ is Hamiltonian. Then we can label the vertices $V = \{v_1, \ldots, v_n\}$ (where $n = |V|$) such that $$\{v_1, v_2\}, \{v_2, v_3\}, \ldots, \{v_{n-1}, v_n\}, \{v_n, v_1\} \in E.$$ Let the above edges be named $e_1, \ldots, e_n$ respectively, and let $F = \{e_1, \ldots, e_n\}$. Note, in particular, that $(V, F)$ is our Hamilton cycle.

Suppose we remove an edge $e$ from $G$ to form $G' = (V, E')$, where $E' = E \setminus \{e\}$. If $e \in E \setminus F$, then all the edges from $F$ are still in $E'$. So, given $v_i, v_j \in V$, without loss of generality assume $i < j$, we can follow the path: $$v_i, e_i, v_{i+1}, e_{i+1}, \ldots, v_{j-1}, e_{j-1} v_j, \tag{$\star$}$$ which connects $v_i$ to $v_j$. Therefore, when $e \in E \setminus F$, $G'$ is connected.

Suppose instead that $e \in F$. Let $k$ such that $e = e_k$. Fix $v_i, v_j \in V$. If $i, j < k$ or if $i, j > k$, then assume without loss of generality that $i < j$. The path described a still connects $v_i$ and $v_j$, and we are done.

Otherwise, $i < k$ and $j > k$, or $i > k$ and $j < k$. Without loss of generality, assume the latter. Then the path $$v_i, e_i, v_{i+1}, e_{i+1}, \ldots, e_{n-1}, v_n, e_n, v_1, e_1, \ldots, e_{j-1}, e_j$$ connects $v_i$ and $v_j$. In any case, $G'$ is connected, so removing a single edge will not disconnect $G$.