\documentclass[11pt,twoside]{article}	
\usepackage{latex-macros/course}
\usepackage{textcomp} % to get \textcent

\newcommand{\cent}{\text{\textcent}}

\renewcommand{\reading}{
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/
handouts/lectures/ln4.pdf} {Week 4 Notes}, Supplementary (optional)
Reading: Rosen \S 7.1-7.4, 7.8, and 8.1 }
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}
\graphicspath{{/toc/a/class/6.042/fall02/problemrepository/figures/}}


%\hidesolutions
%\showsolutions

\begin{document}
\problemset{4}

Note: This problem set contains a number of questions that will
require you to write proofs.  The goal is not only to have correct
proofs, but also to make sure they are clear, orderly, and
well-presented.

%%--------------------------------
%% Rosen 7.8.17
%% Just changed the names of people

\begin{problem}

The EECS department has six committees that meet once a month. How
many different meeting times must be used to ensure that no one is
scheduled to be at two meetings at the same time? The committees are
$C_1 =$ \{Abelson, Meyer, Karger\}, $C_2 =$ \{Meyer, Leiserson,
Rivest\}, $C_3 =$ \{Abelson, Rivest, Karger\}, $C_4 =$ \{Leiserson,
Rivest, Karger\}, $C_5 =$ \{Abelson, Meyer\}, $C_6 =$ \{Meyer, Rivest,
Karger\}. Explain how you arrived at the answer.

\solution{5 meeting times are required.

Draw and color a graph with six nodes, each representing a different
committee.  Connect two nodes with an edge iff there is a conflict
(overlapping members) between the two committees.  This is almost a
complete graph on the six nodes, with only the edge between $C_4$ and
$C_5$ missing.  Now find the minimum coloring.  Since nodes 4 and 5
are not connected, they may be colored the same.  But every other node
must receive a different color since they are all connected to each
other.}
\end{problem}


\begin{problem}
Let $G$ be an undirected graph.  Prove that there is a path from every
vertex of odd degree to some other vertex of odd degree in $G$.

\solution{
\begin{proof}
For some graph $G$, pick an arbitrary vertex $v$ of odd degree. Take the
subset of the graph that is connected to $v$ via some path i.e. the
connected component of $G$ that contains $v$; call this $G_v$. Since $G_v$ is
itself a graph, it must have total degree even, which means there must
be another vertex $w$ of odd degree in $G_v$. Since $G_v$ is connected, that
means there must exist a path between v and another odd degree
vertex. You can do this for any/every odd degree vertex in $G$.
\end{proof}

\begin{proof}
This is an alternate proof by induction on the number of edges, $k$.

Let $P(k)$ be the proposition that there is a path from every vertex of
odd degree to some other vertex of odd degree in $G$, where $G$ has $k$
edges.

The base case of $k=0$ is vacuously true, since all nodes are of even
degree zero.

Given graph, $G$, with $k+1$ edges, there are three cases:
\begin{itemize}
\item     There are no odd degree nodes in $G$; $P(k+1)$ is vacuously true

\item     There is an edge, $g$, from an odd-degree node, $N$, to an even-degree
         node, $M$.

         Remove $g$ to form a $k$-edge graph $H$.  By induction, all
         odd-degree nodes in $H$ have paths to other odd degree nodes in
         $H$.  Note that all nodes besides $M$ and $N$ have the same degree
         in $G$ and in $H$, while $N$ and $M$ switch to having even and odd
         degree, respectively, in $H$.  Hence, any path from an
         odd-degree node in $H$ to another odd-degree node in $H$ will
         also be a path between these nodes in $G$.  So except possibly
         for $N$, all odd-degree nodes in $G$ have paths to other
         odd-degree nodes in $G$.

         But $M$ has odd degree in $H$, and so it has a path in $H$ to an
         odd-degree node, $O$, in $H$.  Of course $O$ =/= $N$, since $N$ is
         even-degree in $H$.  So there is a path in $G$ from $N$ following
         edge $g$ to $M$ to $O$.

         Hence, every odd-degree node in $G$ has a path to another odd-degree
         node.

\item     There is an edge, $g$, from an odd-degree node, $N$, to another
          odd-degree node, $M$.

          As in the previous case, all odd-degree nodes except possibly $M$ and $N$ have
          paths to other odd-degree nodes besides $M$ and $N$.  But the edge $g$
          itself is a length-one path between the odd-degree nodes $M$ and $N$.
          So in fact every odd-degree node in $G$ has a path to another
          odd-degree node.
\end{itemize}
\end{proof}
}

\end{problem}

\begin{problem}
A 2-colorable graph is called {\em bipartite} (two pieces).

\begin{problemparts}
\problempart Prove by induction that every tree is bipartite.

\solution{
We first prove the following claim:

\begin{lemma*}
By a {\em leaf} in a graph, we mean a vertex of degree $1$.  We prove
that every tree on at least $2$ nodes has a leaf.
\end{lemma*}
\begin{proof}
Let $T$ be a tree, and let $P$ be a simple path in $T$ of maximum
length.  (Because we disallow repeated vertices, the length of any
simple path is upper-bounded by the number of vertices in $T$.  This
implies there must be at least one simple path with maximum length.)

Suppose that $P = \{v_1, v_2 \ldots, v_k\}$ in this order.  We claim
that $v_1$ is a leaf.  For if not, then there is an edge $(v,v_1)$ in
$T$, where $v \neq v_2$.  Now if $v \not\in P$, we can attach $v$ to
the end of $P$ to obtain a longer path --- a contradiction.  But if $v
\in P$, then since $v \neq v_2$, this will give a cycle in $T$ ---
also a contradiction.
\end{proof}
Given this fact, we prove the theorem by induction on $n$.
\begin{proof}
Base case: $n = 1$.  We can color the single node anything we want,
thereby using at most two colors.

Inductive step.  Suppose that we know that every tree on $n$ nodes is
bipartite, for some $n \geq 1$.  Let $T$ be a tree on $n+1$ nodes; we
need to show how to two-color it.  Since $n+1 \geq 2$, we know that
$T$ has a leaf $v$.  Let $w$ be the unique neighbor of $v$.  Let $T' =
T - \{v\}$.  Note that $T'$ is a tree, since it is still connected and
has no cycles.  Thus, by the induction hypothesis, we can two-color
it.

Now we define the following two-coloring of $T$.  If $u$ is a vertex
of $T$ not equal to $v$, give $u$ the color that it had in our
two-coloring of $T'$.  Then give $v$ whichever color we didn't give to
its neighbor $w$.  As this is a valid two-coloring of $T$, this
completes the inductive step and the proof.
\end{proof}
}

\problempart Prove that a graph is bipartite {\em if and only if}
every simple cycle is of even length.\footnote{Reminder: for {\em iff}
you need to prove both directions of the implication.\\ \hint
Can $v$ have both an even and an odd length path to $w$?}

\solution{
Assume a graph has a simple cycle of odd length.  Let the cycle be
$v_1,v_2,\ldots, v_n,v_1$, where $n$ is odd. Suppose that two colors
(red and blue) sufficed to color the graph containing this circuit.
Without loss of generality let the color of $v_1$ be red. Then $v_2$
must be blue, $v_3$ must be red, and so on, until finally $v_n$ must
be red (since $n$ is odd). But this is a contradiction, since $v_n$ is
adjacent to $v_1$.  Therefore at least three colors are needed. Hence
a graph is 2-colorable only if every simple cycle is of even
length. 

Conversely, assume the graph has no simple cycle of odd length. We
show that it is possible to color the graph using two colors. Without
loss of generality, assume that the graph is connected. (As otherwise
we can repeat the argument for each connected component of the
graph). Select a node, say $m$, in the graph and color it red. Color
all the nodes adjacent to $m$ blue. Call the set of all such nodes
$S_1$.  Now color all the nodes that are adjacent to the nodes in
$S_1$ but have not yet been colored, red.  Call the set of all such
nodes $S_2$.  Continue this process until you have colored all the
nodes. We now show that no two nodes in $S_i$ are connected by an
edge, for all $i$.  This is sufficient to establish that our coloring
is valid, since two adjacent nodes are either in the same set $S_i$
--- which we are going to show can't happen --- or are in two
consecutive sets $S_i$ and $S_{i+1}$ that are colored differently.
This is true because if one vertex gets included in $S_i$ before its
neighbor is colored, then the neighbor will be colored in the next
step.

Assume that we can find two nodes $u$ and $w$ in some
set $S_i$ that are adjacent in the graph. If $u$ and $w$ are adjacent
to a node in $S_{i-1}$ then we have a simple cycle of length $3$,
which is impossible.  So let $u_{i-1}\neq w_{i-1} \in S_{i-1}$ be
nodes adjacent to $u$ and $w$ respectively.  Now if $u_{i-1}$ and
$w_{i-1}$ are adjacent to a single node in $S_{i-2}$, say $c$, then
$u,u_{i-1},c,w_{i-1},w,u$ is a simple cycle of length 5, which is
impossible.  So let $u_{i-2}\neq w_{i-2}\in S_{i-2}$ be nodes adjacent
to $u_{i-1}$, and $w_{i-1}$ respectively. Continuing this way we
arrive at nodes $u_1\neq w_1 \in S_1$. However these are adjacent to
$m$.  This gives us a simple cycle
$m,u_1,u_2,\ldots,u_{i-1},u,w,w_{i-1},w_{i-2}\dots,w_1,m$, where
$u_j,w_j\in S_j$. But this cycle has length $2i+1$, which is odd,
hence a contradiction. Therefore, for all $i$ we do not have two nodes
in $S_i$ that are connected by an edge.  Therefore our coloring is
valid.  
}

\problempart Explain why (a) follows immediately from (b).
\solution{
Since a tree has no simple cycles, it has no simple cycles of odd
length, and thus (a) follows directly from (b).
}

\end{problemparts}
\end{problem}

%%---------------------------------
%% From a version in Spring02 final
%% modified to remove help on the proof.
%% (rad)

\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 Let the graph $H=\bigl(\{A,B,C,D,E,F\},\, \bigl\{\{A,F\},
\{B,D\}, \{B,E\}, \{C,D\}, \{C,E\}, \{D,E\}\bigr\}\bigr)$. Draw the
graph H and circle the connected components.

%\begin{center}
%\input{/toc/pub/www/classes/6.042/fall01/figures/hex-blank.latex}
%\end{center}

\solution{There are two connected components circled below.
\begin{center}
\input{/toc/pub/www/classes/6.042/fall01/figures/hex-sol.latex}
\end{center}
}

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

\solution{
\mbox{}
\begin{figure}[htb]
\begin{center}
\input{/toc/pub/www/classes/6.042/fall01/figures/j-sol.latex}
\end{center}
\end{figure}}

\problempart Prove the following theorem:

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

\solution{
\begin{proof}
Suppose $G=(V,E)$ is not connected. Let $a, b$ be any two vertices 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$. 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
component, then they are connected in $G^c$.

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 is connected.
\end{proof}
}

\problempart However the converse of this theorem 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.

\solution{Many solutions are possible.  One is shown below.  Another
is that $G^c$ is a graph on 4 nodes arranged as a square with three edges
forming the letter Z.  Then $G$ has its three edges forming the letter N.

\begin{figure}[htb]
\begin{center}
%\centerline{\resizebox{!}{5in}{\includegraphics{/toc/pub/www/classes/6.042/fall01/figures/partd}}}
\includegraphics[width=2.5in]{/toc/pub/www/classes/6.042/fall01/figures/partd.jpg}
%\input{/toc/pub/www/classes/6.042/fall01/figures/partd.pdf}
\end{center}
\end{figure}

}
\end{problemparts}
\end{problem}


% pset 6, #3
\begin{problem} \textbf{The Touring Knight} \\
%% Remove the Rosen cite, since the last problem is an odd exercise %%
A knight is a chess piece that can move either two spaces horizontally
and one space vertically or one space horizontally and two spaces
vertically.  That is, a knight on square $(x, y)$ can move to any of the
eight squares $(x \pm 2, y \pm 1), (x \pm 1, y \pm 2)$, if these squares
exist on the chessboard (which is normally 8 $\times$ 8).

A knight's tour is a sequence of legal moves by a knight starting at
some square and visiting each square exactly once.  A knight's tour is
called reentrant if there is a legal move that takes the knight from
the last square of the tour back to where the tour began.  We can
model knight's tours using the graph that has a vertex for each square
on the board,with an edge connecting two vertices if a knight can
legally move between the squares represented by these vertices.
\begin{problemparts}

\problempart 
Show that finding a reentrant knight's tour on an $m
\times n$ chessboard is equivalent to finding a Hamilton circuit on
the corresponding graph. 

\solution{In a Hamiltonian circuit, we need to visit each vertex once
moving along the edges and returning to the starting point. A
reentrant knight's tour is precisely such a circuit, since we visit
each square once, making legal moves, and return to the starting
point.}

\problempart Show that the graph representing the legal moves of a
knight on a $m \times n$ chessboard, wherever $m$ and $n$ are positive
integers, is {\em bipartite}.

\solution{Each square of the board can be thought of as a pair of
integers $(x,y)$. Let $A$ be the set of squares for which $x+y$ is
odd, and let $B$ be the set of square for which $x+y$ is even. This
partitions the vertex set of the graph representing the legal moves of
a knight on the board into two parts. Now every move of the knight
changes $x+y$ by an odd number -- either $1+2=3$, $2-1=1$, $1-2=-1$,
or $-1-2=-3$. Therefore every edge in this graph joins a vertex in $A$
to a vertex in $B$. Thus the graph is bipartite.}

\problempart Deduce that there is no reentrant knight's tour on an $m
\times n$ chessboard when $m$ and $n$ are both odd.

%(\emph{Hint:} Problem Set 4, problem 3.)

\solution{Since there are $mn$ squares on the $m \times n$ board, if
both $m$ and $n$ are odd, there are an odd number of squares. Since by
part (b), the corresponding graph is bipartite, from PS 4, problem 3,
we know that it has no cycle of odd length, \emph{i.e.} it has no
Hamilton circuit (since there are an odd number of nodes). Hence,
there is no reentrant knight's tour.}

\end{problemparts}
\end{problem}


\end{document}                            


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

Extra Unused problems



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\begin{problem}

Some properties of a simple graph, $G$, are described below.  For each
property, carefully prove or give a counterexample to the claim that the
property is {\em invariant under isomorphism} ({\em cf.} Rosen, p.455).

\begin{problemparts}
\problempart
$G$ has an even number of vertices.

\solution{It is invariant under isomorphism. There must be an
one-to-one and onto mapping between the vertices of two isomorphic
graphs. Therefore, the number of vertices in the two graphs must be
the same. If one graph has even number of vertices, then the other
must have even number of vertices.}

\problempart
None of the vertices of $G$ is an even integer.

\solution{It is not invariant under isomorphism. We do not really care
what the vertices are. Vertices can be any kind of mathematical
objects.  All we are interested is that whether there exists a
one-to-one and onto function $f$ mapping from vertices of one graph to
vertices of another with the property that $a$ and $b$ are adjacent in
the first graph if and only if $f(a)$ and $f(b)$ are adjacent in the
second graph, for all $a$ and $b$ in the first graph.

So, for example, let $G_1$ be a graph with a single vertex, 1, and $G_2$ be
a graph with a single vertex, 2. Obviously the two graphs are isomorphic, but
$G_2$ does not have vertices which are even integers.}

\problempart
$G$ has a vertex of degree 3.

\solution{It is invariant under isomorphism.  

Let $G_1, G_2$ be simple graphs and $f:V_1\to V_2$ be an isomorphism
between them.  Suppose $v\in V_1$ has degree 3; we want to show that there
is a vertex of degree 3 in $V_2$.  In fact, we'll show that $f(v)$ has
degree 3.
 
Since $v$ has degree 3, there are exactly 3 vertices adjacent to $v$; say
these are $v_1,v_2,v_3$.  Since $f$ is a bijection, $f(v_1),f(v_2)$ and
$f(v_3)$ are all distinct.  Since there is an edge between $v$ and $v_i$
in $G_1$, the definition of isomrphism implies that there is an edge
between $f(v)$ and $f(v_i)$ for $i=1,2,3$, so the degree of $f(v)$ is at
least 3.
 
We now prove by contradiction that the degree of $f(v)$ is at most 3.
Suppose $f(v)$ had degree $>3$.  This means there is a vertex $w \in V_2$
which is not equal to $f(v_1), f(v_2),$ or $f(v_3)$, but is also adjacent
to $f(v)$.  Since, $f$ is a bijection, there is a vertex $v_4 \in V_1$
such that $f(v_4) = w$ and $v_4 \neq v_i$ for $i=1,2,3$.  Since $w=f(v_4)$
is adjacent to $f(v)$, the definition of isomorphism implies that $v_4$ is
adjacent to $v$, contradicting the fact the $v_1,v_2,v_3$ were exactly the
vertices adjacent to $v$.}


\problempart
$G$ has exactly one vertex of degree 3.

\solution{It is invariant under isomorphism.

Prove by contradiction:  Let a graph $G_1$ has exactly one vertex of 
degree $3$ while another graph $G_2$ does not have exactly one vertex of 
degree 3. Suppose the two graphs are isomorphic. If $G_2$ does not have 
a vertex of degree 3, then from part (c), there is a contradiction.
If $G_2$ has more than one vertices of degree 3, then there must
be at least one vertex in $G_2$ of degree 3 which is mapped to 
a vertex of degree $\neq 3$ in $G_1$. Since two vertices of different degrees
are mapped from $G_1$ to $G_2$, using the same argument from part (c),
it reaches a contradiction. Therefore, if $G_1$ has exactly one 
vertex of degree 3 , then $G_2$ must also have exactly one 
vertex of degree 3.}


\problempart
One of the vertices of $G$ is also an edge of $G$.

\solution{It is not invariant under isomorphism. 

Let $G_1$ be a graph with three vertices, $1$, $2$ and $\{1,2\}$. There is
only one edge from vertex $1$ to vertex $2$. Therefore, $\{1,2\}$ is a vertex
of $G_1$ and also an edge of $G_1$. 

On the other hand, let $G_2$ be a graph with three vertices,
$7$, $12.1$ and an ordered pair $(1, -3)$(note: these are somewhat
tasteless, but legitimate things to use as vertices). There is only 
one edge from vertex $7$ to vertex $12.1$.
Obviously two graphs are isomorphic; however, $G_2$ does not have 
a vertex which is an edge at the same time. 
Therefore, it is not invariant under isomorphism.}

\end{problemparts}
\end{problem}

\begin{problem}
The adjacency matrix of a graph is given below.

\[
\left[
\begin{array}{cccccc}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0
\end{array}
\right]
\]
\begin{problemparts}

\problempart Draw the graph defined by this adjacency matrix.  Label
the vertices of your graph $1, 2, \ldots, 6$ so that vertex $i$
corresponds to row and column $i$ of the matrix.

\solution{ 
\begin{center}
\includegraphics[width=2in,height=2in]{adjgraph}
\end{center}
%%\centerline{\resizebox{!}{2.0in}{\includegraphics{figures/adjgraph}}}
}

\problempart Give a coloring of the vertices that uses the minimum
number of colors. Prove that this a minimum coloring.

\solution{The diagram above shows a 3-coloring.  The chromatic number
cannot be less than 3, because vertices 1, 2, and 4 are all connected
and therefore must receive distinct colors.  Consequently, the
chromatic number of the graph is exactly 3.}

\end{problemparts}

\end{problem}





%-----------------------------------------------
% source: Rosen 7.8.21 (rewritten to be more clear)
% topics: coloring application (register coloring)
% last used: first time
\begin{problem}
My computer program has seven variables, {\tt t,u,v,w,x,y,z},
and computes in 6 steps. The steps in which each variable is used are
as follows: {\tt t:} steps 1 through 6; {\tt u:} step 2; {\tt v:}
steps 2 through 4; {\tt w:} steps 1,3 and 5; {\tt x:} steps 1 and 6;
{\tt y:} steps 3 through 6; {\tt z:} steps 4 and 5. Each variable will
need to occupy the same index register at each one of the steps in
which it is going to be used; however during the steps when the
variable is not being used the register may be used by some other
variable. How many such registers are needed for my program? Explain
how you arrived at the answer.

\solution{This problem shows an application of graph coloring to
register allocation in a processor. Consider a simple graph $G$ having
the seven variables as its nodes, and an edge between two variables
iff there is at least one step of the program during which both
variables are going to be used.  Figure~\ref{fig:vars} contains the
graph we are talking about.

\begin{figure}
\begin{center}
\unitlength=0.035pt
\input{/toc/pub/www/classes/6.042/fall01/figures/ps4-4a.latex}
\end{center}
\caption{}
\label{fig:vars}
\end{figure}

Clearly, two variables have to occupy different index registers iff
they are going to be used simultaneously sometime during the
progam execution, that is, iff they are connected in~$G$. 

To correctly and economically assign variables to registers means to
map each variable to one register in a way that does not cause
collisions (two simultaneously used variables mapped to the same
register) and uses as few registers as possible. But (if we think of
registers as colors) this is the same as to color $G$ in a way that
does not cause neighboring vertices of the same color and uses as few
colors as possible. So, we have reduced the original problem to the
problem of coloring~$G$.

Figure~\ref{fig:varscol} shows such a coloring, using 5 colors. To see
that this is the minimum one, just notice that variables $t$, $v$,
$w$, $y$, and $z$ form a 5-vertex subgraph which is complete, and
hence cannot be colored with less than~5 colors.

\begin{figure}
\begin{center}
\unitlength=0.035pt
\input{/toc/pub/www/classes/6.042/fall01/figures/ps4-4b.latex}
\end{center}
\caption{}
\label{fig:varscol}
\end{figure}

SIDE NOTE: In this problem we have assumed that a variable must always
use the same register, i.e. a variable is assigned a single
color. However in a real compiler this is overly restrictive because a
variable is backed up into memory every time it is evicted from the
register set and then reloaded from memory into the register set when
it needs to be used again. When it is reloaded there is no reason why
the same register must be used. For example, say we had a variable $x$
which is used in steps 1,2,3 and then later used in step 6. Then $x$
could be stored in register $r1$ for steps 1 through 3 and some other
register $r2$ for step 6. We can still use coloring to solve the
problem by treating $x$ as two separate variables: $x_{123}$ and
$x_6$. Since the number of variables in a computer program can be very
large and the register set of a processor is typically much smaller
(16-64 registers), register allocation is an important piece of
compiling.

}

\end{problem}






\begin{problem}
An undirected graph $G$ is {\em self-complementary} if $G$ and
$\bar{G}$ are isomorphic. $\bar{G}$ is the complement of $G$ as
defined in problem 4.

% The symbol $\bar{G}$, where $G$ is a graph, is defined in problem 33
% on page 456 of Rosen. The term ``isomorphic'' is defined on page 460
% of Rosen.

\begin{problemparts}

\problempart Draw a self-complementary graph with more than one
vertex.

\solution{The simplest solution is given below.  Edges of the graph
are shown with solid lines, and edges of the complement are shown with
dotted lines.

\begin{center}
\includegraphics[width=1.5in]{/toc/pub/www/classes/6.042/fall01/figures/selfcomp}
%%\centerline{\resizebox{!}{1.5in}{\includegraphics{figures/selfcomp.eps}}}
\end{center}

}

\problempart Give a formula for the number of edges in the complete
graph with $n$ vertices.  No proof is required.

\solution{In a complete graph, each of the $n$ vertices is joined by
edges to $n-1$ other vertices.  However, this counts every edge twice,
once for each endpoint.  Therefore, the number of edges in the
complete graph with $n$ vertices is

\[
\frac{n(n-1)}{2}.
\]
}

\problempart Show that if a graph $G$ is self-complementary, then the
number of vertices in $G$ is congruent to either 0 or 1 mod 4 (hint:
use part (b)).

\solution{Let $m$ be the number of edges in $G$, let $\bar{m}$ be the
number of edges in the complementary graph $\bar{G}$, and let $n$ be
the number of vertices in each of these graphs.  If $G$ is
self-complementary, then $m$ and $\bar{m}$ must be equal.  Futhermore,
every edge in the complete graph on $n$ vertices is contained in
exactly one of the graphs $G$ and $\bar{G}$.  Therefore, $m + \bar{m}
= \frac{n(n-1)}{2}$.  Putting these two facts about $m$ and $\bar{m}$
together, we find that

\[
m = \bar{m} = \frac{n(n-1)}{4}.
\]

Since the number of edges in a graph must be an integer, $n (n-1)$
must be a multiple of 4.  That is, a self-complementary graph must
satisfy

\begin{eqnarray*}
n (n-1) \equiv 0 \pmod{4}.
\end{eqnarray*}

This congruence holds exactly when the number of vertices $n$ is
congruent to 0 or 1 mod 4.
}

\end{problemparts}

\end{problem}


