\problemdata                                                             
        {Counting Complete Graphs} % latex-friendly label for the prob.
        {counting} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Final, 5} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
A \emph{complete} graph is a special kind of graph in which every pair of vertices is connected by an edge. Figure \ref{complete} depicts a complete graph on 5 vertices.
\begin{figure}[h]
\begin{center}
\includegraphics[height=5 cm,keepaspectratio=true]{K5}
\caption{A complete graph on 5 vertices}
\label{complete}
\end{center}
\end{figure}
 
Suppose you have a set of $n$ different (labeled) vertices.

\begin{problemparts}

\problempart
How many \emph{complete} graphs are there on $n$ vertices?

\solution{
One.
}

  
\problempart How many simple paths are there in a complete graph?
\hint How many simple paths of length~$i$ are there?

\solution{ Recall that a path is a sequence of vertices (from one
  to $n$ vertices) with no cycles.  Since order matters, for each path
  length $i$ ($1 \leq i \leq n$), we choose an $i$-permutation of the
  $n$ vertices, which can be done $n! \over (n-i)!$.  Summing over all
  path lengths gives
  \[\sum_{i=1}^{n} {n! \over (n-i)!}\]
  }


\problempart How many graphs (not necessarily complete) are there
on $n$~vertices?  

\solution{ $2^{\binom{n}{2}}$ (for each possible edge, we choose
  whether it's in the graph or not).}


\problempart How many simple cycles are there in a complete graph?
(Recall that a simple cycle is a simple path containing at least three
edges that starts and ends at the same vertex.  Consider cycles with
the same edges to be equivalent, even if their starting vertices are
different.)  Your answer need not be in closed form; it can involve
summations.

\solution{
  Let's count cycles of length $i$, then sum for $i = 3, 4, \ldots,
  n$.  (Usually we don't consider a cycle to be simple unless it
  contains at least three vertices, and no vertex appears more than
  once.)  To count the number of cycles with exactly $i$ vertices,
  there are $\binom{n}{i}$ choices for the $i$~vertices in the cycle,
  $i!$~ways of ordering $i$~vertices, but each cycle is actually being
  overcounted by a factor of~$i$ (since any vertex could be the start
  vertex), and a factor of~$2$ because a cycle is counted once for
  each possible direction of traversal. (It would also be reasonable
  not to divide by 2, since it makes sense to specify a direction for
  a cycle, e.g., if the graph is directed.)  Summing over all possible
  values of~$i$ gives the answer:
  \begin{displaymath}
    \frac{1}{2} \sum_{i=3}^{n} \binom{n}{i} (i-1)!
  \end{displaymath}
}

\end{problemparts}
\end{problem}
                                 