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


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

% 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.

\solnospace{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]{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.

\solnospace{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)).

\solnospace{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}