\problemdata     
{graphs-6}           
{graphs, connectivity}             
{}              
{S02 in-class Week 4} 		
{S02 Radhika}        	


\begin{problem}
An edge of a connected graph is called a {\em cut-edge} if
removing the edge disconnects the graph.

\begin{figure}[h]
\begin{center}
\begin{picture}(120,40)

% top row
% line start/slope/length
\put(00,40){\circle*{3}}  \put(00,40){\line(1,0){40}}
                          \put(00,40){\line(1,-1){20}}
\put(40,40){\circle*{3}}  \put(40,40){\line(1,-1){20}}
                          \put(40,40){\line(-1,-1){20}}
\put(100,40){\circle*{3}} \put(100,40){\line(0,-1){40}}
                          \put(100,40){\line(1,-1){20}}
% second row
\put(20,20){\circle*{3}} \put(20,20){\line(0,-1){20}}
\put(60,20){\circle*{3}} \put(60,20){\line(1,0){60}}
                         \put(60,20){\line(0,-1){20}}
\put(120,20){\circle*{3}} \put(120,20){\line(-1,-1){20}}

% bottom row
\put(20,00){\circle*{3}} \put(20,00){\line(1,0){40}}
\put(60,00){\circle*{3}}
\put(100,00){\circle*{3}}

% put A and B
\put(50,30){A}
\put(75,10){B}

\end{picture}
\end{center}
%%\centerline{The line graph $L_4$}
%%\label{fig:cut}
\end{figure}

\begin{problemparts}
\problempart In the above figure, are either A or B cut-edges? Explain.

\solution{
A is not a cut-edge, B is.

If we remove the edge A the two vertices remain connected because
there is another path between those vertices. If we remove B there is
no path from the end vertices to each other, hence the vertices get
disconnected thus disconnecting the graph.

More succinctly, A is part of a cycle and B is not.
}

\problempart Prove that in an undirected connected graph, an edge $e$
is a cut-edge \emph{if and only if} no simple cycle contains $e$.


\solution{
\begin{proof}
Since there is an {\em if and only if} we need to prove both sides of
the implication --- that if an edge is part of a simple cycle then it
can not be a cut-edge, and if an edge is not part of a simple cycle
then it must be a cut-edge. We will use both directions of this
implication to prove parts b) and c).

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 $u$ and $v$.  We must show
that there still exists a path between $u$ and $v$ after edge $e$ is
removed.  Let $e, e_1, e_2, \ldots, e_n$ be the edges in a simple
cycle containing $e$.  Since the cycle is simple, none of the edges
$e_1, e_2, \ldots, e_n$ are equal to $e$.  Therefore, we can construct
a new path that connects $u$ and $v$, but does not contain edge $e$ by
substituting either $e_1, e_2, \ldots, e_n$ or $e_n, e_{n-1}, \ldots,
e_1$ in place of edge $e$ in the path $P$.This shows that the graph
remains connected after edge $e$ is removed, and so edge $e$ is not a
cut-edge.

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
(p.464 in ed.3), 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 of edge edge $e$ even after edge $e$ is
removed from the graph.  Adjoining edge $e$ to path $P$ gives a simple
cycle containing edge $e$.
\end{proof}
}

\problempart Using the previous part, argue that in a tree every edge
is a cut-edge but in an $n \times n$ mesh no edge is a cut-edge. Why
might this be important?

\solution{

For the tree we can simply state that since a tree is acyclic, every
edge is a cut-edge.

For a mesh, when $n=1$, the claim is trivially true because the mesh
contains no edges. But if $n>1$, every edge is part of a cycle:
consider a horizontal edge between adjacent nodes $a_1, a_2$ on the
same row.  Consider the two nodes $b_1, b_2$ either immediately above
or immediately below $a_1, a_2$.  Then $b_1$ is connected to $b_2$
(adjacent nodes on same row); $a_1$ is connected to $b_1$ and $a_2$ is
connected to $b_2$ (adjacent nodes on same column).  So
$a_1-b_1-b_2-a_2$ forms a cycle. Likewise, every vertical edge is part
of a square cycle.  So every edge is part of a cycle, and hence cannot
be a cut-edge. In fact the non-border edges are part of many cycles.

Cut-edges can be an important concept because they point out weak
points that can cause total failure --- consider the graph of utility
lines or a network of processors in a parallel computer. The more
edges you need to remove in order to disconnect the graph the better.}

\end{problemparts}
\end{problem}

