% Spring 00 Quiz 1
% Spring 95 Quiz 1
% Modified significantly, Radhika

\begin{problem}[20]
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}

% CANNOT FIGURE OUT WHAT IS WRONG
% current hex-blank.pdf has too much extra space, Generated new one
% using epstopdf,looks ok in acroread but then when included gets all 
% messed up. Deleted it and left old pdf,

\iffalse
\problempart[5] Fill in the edges for graph H and circle the connected
components.

$H=\bigl(\{A,B,C,D,E,F\},\, \bigl\{\{A,F\}, \{B,D\},
\{B,E\}, \{C,D\}, \{C,E\}, \{D,E\}\bigr\}\bigr)$.

\begin{figure}[htbp]
\centering \includegraphics[height=2in]{figures/hex-blank}
\end{figure}
\fi

\begin{center}
\input{hex-blank.latex}
\end{center}

% substitution, for conflict exam

\problempart[5] Draw the graph H and circle the connected components.

$H=\bigl(\{A,B,C,D,E,F\},\, \bigl\{\{A,F\}, \{B,D\},
\{B,E\}, \{C,D\}, \{C,E\}, \{D,E\}\bigr\}\bigr)$.

\vspace{3in}

\solution{There are two connected components circled below.
\begin{figure}[htb]
\centering \includegraphics[height=2in]{figures/hex-sol}
\end{figure}
}

\problempart[2] Let the graph $J=\bigl(\{A,B,C,D\},\, \bigl\{\{A,B\},
\{C,D\}\bigr\}\bigr)$. Draw the complement of $J$.

\solution[\vspace*{1.5cm}]{\begin{figure}[htb]
\begin{center}
\centering \includegraphics[height=2in]{figures/j-sol}
\end{center}
\end{figure}}

% \problempart[1] Draw the complement of $H$.

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

\newpage
\problempart[13] Complete the following proof.

\begin{theorem}
If an undirected graph $G$ is not connected then $G^c$ is connected.
\end{theorem}

\begin{proof}
Suppose $G=(V,E)$ is not connected. Let $a, b$ be any two vertices in
in $V$.  Consider the following two cases:
\begin{description}

\item[Case 1:] If nodes $a$ and $b$ are in different connected
components of $G$, then they are connected in $G^c$. FILL IN PROOF:

\solution[\vspace*{6cm}]{Then there is no edge in $E$ connecting $a$
and $b$.  Thus $G^c$ contains an edge connecting $a$ and $b$ by definition.}

\item[Case 2:] If nodes $a$ and $b$ are in the same connected compenent,
then they are connected in in $G^c$. FILL IN PROOF:

\solution[\vspace*{6cm}]{Let $c$ be a vertex in a different connected
component. We are guranteed that such a vertex exists because we know
that $G$ is disconnected therefore it must contain more than one
connected components. 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$ and so it is connected.
\end{proof}

\iffalse
\problempart[5] However the converse is not true: if $G^c$ is connected,
then $G$ is not necessarily disconnected. Give an example of a
connected graph whose complement is also connected (\hint A 4 node
graph is sufficient).

\solution[\vspace*{3cm}]{The example that I come up with is 4 nodes
connected in a line. Or another way of drawing the same example is
four nodes in a Z, the complement is a Z on its side. Is this too
right? Is this too hard?

\begin{figure}[htb]
\begin{center}
 \centerline{\resizebox{!}{5in}{\includegraphics{figures/partd}}}
\end{center}
\end{figure}

}
\fi
\end{problemparts}
\end{problem}

\comment{Radhika}{part (b), basically to build intuition befoere the
proof, weigh it very low}

\comment{Radhika}{I structered the proof part to address the comment
from earlier exam that students couldn't figure in real time which
method to use to prove the thoerem. The prupose of the hint is to tell
them which method to use, and then see how well they can apply the
method.}

\comment{Tina}{Added in graphic to help to make part a easier to graph
and added in graphics for both solutions for part a and b and d.
Please check these!}

\iffalse
\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.

\fi
