\problemdata                                                             
        {connected components, graph complement} % latex-friendly label for the prob.
        {graphs, proofs} % The topic(s) of the problem content.  
        {Spring 1995, Q1} % Source (if known)                                          
        {S01 Quiz 1, 6} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
The {\em complement} of an undirected graph $G=(V,E)$ is the graph 
$G^c=(V,E^c)$. 
That is, $G^c$ contains exactly those edges that are not in $G$. 

\begin{problemparts}
\problempart  What are the connected components of the following graph
$H$?:\\ $H=\bigl(\{A,B,C,D,E,F\},\, \bigl\{\{A,F\}, \{B,D\},
\{B,E\}, \{C,D\}, \{C,E\}, \{D,E\}\bigr\}\bigr)$

\solution{
The connected components are {[G1],[G2]}.

\begin{figure}[htbp!]
 \centerline{\resizebox{!}{1.5in}{\includegraphics{figs/prob6a}}}
\end{figure}

}


\problempart  Draw the complement of H.

\solution{

\begin{figure}[htbp!]
 \centerline{\resizebox{!}{1.5in}{\includegraphics{figs/prob6b}}}
\end{figure}
}


\problempart Prove that if an undirected graph~$G$ is not connected
then $G^c$ 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 $G^c$.
\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 $G^c$
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 $G^c$ contains a path from $a$ to $b$, for any pair of vertices
$a, b$ in $V$.  Thus $G^c$ is connected.

\paragraph{Comments} Most people got parts (a) and (b) correctly. These were intended to give you some intuition on how $G^c$ relates to $G$ and help you answer part (c). Few people got full credit on part (c). Many confused the definition of a connected graph with that of a \emph{fully} connected graph, even thought they had gotten part (a) right! \par Many assumed that using induction was the way to go. Not very surprisingly, given the prominent role that this method has been given in the first part of the course. Unfortunately, in this case, induction doesn't work. Those who did get it right using induction basically used the argument presented in the solution, which makes the inductive argument superfluous. The most common issue in incorrect inductive attempts involved \emph{buildup errors}.
\par Others attempted to prove the claim \emph{by contradiction}. While this made their life slightly more difficult, some actually succeeded. The most common mistake using this approach was the failure to examine the case that two vertices come from the \emph{same connected component} in the original graph.
\par Only a handful of students used the straightforward approach presented in the solutions.    
                                                                                              
}

\end{problemparts}
\end{problem}
                                 