In an undirected connected simple graph G = (V, E), an edge e ∈ E is called a cut edge if G − e has at least two nonempty connected components.
Prove: An edge e is a cut edge in G if and only if e does not belong to any simple circuit in G. This needs to be proved in each direction.
Typically I would write where I am for a problem like this, but I have no idea how to approach this proof, especially why it needs to be proved in each direction (what is the significance of this?). Any and all help would be much appreciated.
Best Answer
Given a simple undirected connected graph $G = (V,E)$. Edge $e \in E$ is called a cut edge if $G^\prime = (V,E-\{e\})$ has at least two non-empty connected components.
Theorem. The edge $e \in E$ is a cut edge $\Leftrightarrow$ $e$ does not belong to a circuit in $G$.
$\Rightarrow$ Suppose $e \in E$ does belong to a circuit in $G$. Then, this circuit can be described as $e_1,\ldots,e_k$, with $e = e_i$ for some $1 \leqslant i \leqslant k$. Remove any $e_i$ in this circuit still allows the traversal $e_{i+1},\ldots,e_k,e_1,\ldots,e_{i-1}$, so $G$ is still connected, hence $e$ can not be a cut edge. Contradiction.
$\Leftarrow$ Suppose that after removing $e = \{v_1,v_2\}$ then $G$ is still connected. Then, consider the trail from $v_1$ to $v_2$. Adding $e$ to this trail creates a circuit (so there is a circuit in the original graph), hence a contradiction.