\problemdata
{graphs}
{S00 ps4}
{cut-edge}
{simple cycle}

\begin{problem}
An edge of a connected graph is called a {\em cut-edge} if removing
the edge disconnects the graph.  Prove that an edge $e$ in a connected
graph $G$ is a cut-edge if and only if no simple cycle contains $e$.


\solution{
  First, we prove that if $e$ is contained in a simple cycle, then $e$
  is not a cut-edge.  Since $G$ is connected, there exists a path $P$
  between every pair of distinct vertices.  We must show that this
  remains true after $e$ is removed.  We will do this by considering
  the two nodes $u$ and $v$ on each side of $e$, and showing that $u$
  and $v$ must still be connected by a different path $P_2$ when $e$
  is removed.  This shows that all original paths between any two
  vertices in the path can be changed to include the path $P_2$ where
  the edge $e$ used to be.  Let us write out the simple cycle that
  contains $e$ as $u,v,v_1,v_2,\dots,v_n,u$.  Because it is a simple
  cycle, all vertices are distinct (except for the double occurrence
  of $u$).  This means that the edge $e$ only occurs once in the
  cycle.  When $e$ is removed we can't travel along $(u,v)$, however
  we can use the path $u,v_n,\dots,v_2,v_1,v$.  This implies that all
  vertices are still connected in the graph, because we have a
  ``detour'' around $e$ when it is cut.

Next, we prove that if $e$ is not a cut-edge, then $e$ is contained in
a simple cycle.  We will make use of Theorem 1 on page 469 of Rosen,
which states that there is a {\em simple} path between every pair of
distinct vertices in a connected graph.  Since $e$ is not a cut-edge,
the graph obtained by removing edge $e$ is connected.  So by the
theorem, there exists a simple path $P$ connecting the endpoints $u$
and $v$ of edge $e$, even after $e$ is removed from the graph.  Let
$P=v,v_1,v_2,\dots,v_n,u$.  The path is simple so adjoining edge $e$
to the end of $P$ gives a simple cycle containing edge $e$.
Specifically, $v,v_1,v_2,\dots,v_n,u,v$.
}

