        \problemdata       % Takes 5 *mandatory* arguments
        {graph-compl-conn}             % latex-friendly label for the prob.
        {graphs}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 PS4-5, S95 Q1} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).


\begin{problem}

%-----------------------------------------------
% source: Spring 95 Quiz 1, pRepository
% topics: graph connectivity

The {\em complement} of an undirected graph $G=(V,E)$ is the
graph $\bar{G}=(V, \bar{E})$.  That is, $\bar{G}$ contains exactly
those edges that are not in $G$.  Prove that if $G$ is not connected
then $\bar{G}$ is.

\solution{
  Suppose $G=(V,E)$ is not connected.  Then $G$ can be divided into
  nonempty disjoint connected components $G_1, G_2, \ldots G_k$ (where
  $k>1$).  Consider any two vertices $a, b$ in $V$.  Let's show that they
  are connected by a path in $\bar{G}$.
\begin{description}

\item[Case 1]  \ $a$ and $b$ are in different connected components of
$G$.  Then there is no edge in $E$ connecting $a$ and $b$.  Thus $\bar{E}$
contains an edge connecting $a$ and $b$.

\item[Case 2]  \ $a$ and $b$ are in the same connected component of
$G$.  Let $c$ be a vertex in a different connected component.  By case
1, $a$ and $c$ are connected, as are $b$ and $c$.  Thus $a$ and $b$ are
connected through $c$.

\end{description}
Thus $\bar{G}$ contains a path from $a$ to $b$, for any pair of vertices
$a, b$ in $V$.  Thus $\bar{G}$ is connected.
}

\end{problem}