If G is a connected Graph with a cycle, if you remove an edge from the cycle then G is still connected

Question

The proof is quite obvious but how do you write it down nicely? I have this problem a lot with graph theory proofs where I don't know how to write them down so that they are rigorous enough.

The proof itself would go something like this:

Let C be a cycle in G.If we remove the edge e = {u, v} from C then C becomes a path between u and v. C is still connected so G is also still connected.

Answer 1

$G$ is connected $\iff$ every pair of vertices are connected.

Let's take any two vertices $u$ and $v$. Since the original $G$ is connected, we can choose a path between $u,v$. If the removed edge is not a part of the path, then in the new graph, say $G'$, this path is still viable. If not, since the removed edge is in a circle, we can replace it by the rest of the circle. Hence we can always find a path between any pair of vertices.

Answer 2

I would write something like this: Let $G$ be a connected graph with a cycle $C= (c_1, \ldots, c_k)$. Let $v_1, v_2$ be arbitrary vertices in $G$ and let $(e_1, \ldots, e_n)$ be a path from $v_1$ to $v_2$ (which exists since $G$ is connected). To show that after removing some edge $c_j$ from the cycle, the resulting graph is still connected, it suffices to show that there exists a path $(e_1', \ldots, e'_m)$ from $v_1$ to $v_2$ such that $e'_i \neq c_j$ for all $1 \leq i \leq m$.

To do this, note that if $e_i \neq c_j$ for all $1 \leq i \leq n$, then we can take $(e_1', \ldots, e'_m) = (e_1, \ldots, e_n)$ and we're done.

Otherwise, $e_i = c_j$ for some $1 \leq i \leq n$. Now, we can assume that $e_i$ is the only such $i$ (either we can define paths as being injective, or otherwise we can also assume that $(e_1, \ldots, e_n)$ has no repeating edges. If this is not clear, just ask). Now we use that $C$ is a cycle, so we can use the other edges in the cycle to replace $c_j$. More precisely, the path $$ (e_1, \ldots, e_{i-1}, c_{j-1}, c_{j-2}, \ldots, c_1, c_n, c_{n-1}, \ldots,c_{j+1}, e_{i+1}, \ldots, e_n) $$ will be a path from $v_1$ to $v_2$ which doesn't contain $c_j$. Since $v_1,v_2$ were arbitrary, this concludes the proof.

You could go into even more detail (by proving for example that the given path really works by using the definition of edges as ordered pairs of vertices), but unless you're in an introductory proof class or something you'll probably want less detail, not more.

Answer 3

We are given that there is a cycle containing the edge $uv$. Because $u$ and $v$ are part of the cycle there are at least two paths from $u$ to $v$: we can go directly from $u$ to $v$ along the edge $uv$ or we can go in the other direction in the cycle and end up at $v$. The same argument shows that there are at least two paths from $v$ to $u$.

Suppose $P=x,v_1,\dots v_n,y$ is a path from $x$ to $y$ in $G$. If the edge $uv$ is not in $P$ then $P$ remains unchanged when we remove $uv$. If $uv$ is contained in $P$ then when we get to $u$, we can go around the cycle to get to $v$ and then continue to $y$. Since this is true for any path in $G$, we conclude that removing $uv$ leaves $G$ connected.