\documentstyle[12pt,twoside]{article}
\input{macros-course}

\addtolength{\textheight}{.05in}
\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

\problem
The vertices of any directed graph may be partitioned into {\em strongly
connected components}.  Two vertices $i$ and $j$ belong to the same strongly 
connected component if there is some path from $i$ to $j$ and some path 
from $j$ to $i$.  \\
Theory pig notices an interesting phenomenon.  He starts with a graph
and partitions it into strongly connected components.  He then removes
all edges which connect two vertices contained in the same component, and
notices that the graph which remains has no cycles.  Prove that this will
always be true.\\

{\bf Solution:}\\
\begin{proof}
Proof by contradiction\\
Consider an arbitrary graph $G = (V,E)$.  Let $G' = (V,E')$ be the graph 
which remains when all edges of $G$ connecting two vertices in the same 
strongly connected component are removed. \\

Suppose that $G'$ has a cycle.  Let $i_1$, $i_2$, ..., $i_k$ denote the
nodes in this cycle.  We know that there is $i_1$ a path from $i_1$ to $i_2$,
since they are connected in a cycle.  Similarly, we know there is a path
from $i_2$ to $i_1$.  However, this implies that $i_1$ and $i_2$ should have
been in the same strongly connected component in $G$, and the edge from $i_1$ 
to $i_2$ should have been removed when forming $G'$.  Since the edge was not
removed, we have a contradiction, which implies that $G'$ has no cycles.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}

