        \problemdata       % Takes 5 *mandatory* arguments
        {graph-algo}           % latex-friendly label for the prob.
        {Graphs, Trees, State Machines, Counting, Well-order} %topic(s) of the problem content.
        {}               % Source (if known)
        {F01 q2-3, F99 Q2-4} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
 
We apply the following operation to a \textbf{simple graph} $G$:
pick two vertices $u \neq v$ such that either
\begin{enumerate}
\item there is an edge of $G$ between $u$ and $v$ and there is also a path
from $u$ to $v$ which does \emph{not} include this edge; in this case,
delete the edge $\set{u,v}$.

\item there is no path from $u$ to $v$; in this case, add the edge
$\set{u,v}$.
\end{enumerate}

Keep repeating these operations until it is no longer possible to find two
vertices $u \neq v$ to which an operation applies.

Assume the vertices of $G$ are the integers $1,2,\dots,n$ for some $n \geq
2$.  This procedure can be modelled as a state machine whose states are
all possible simple graphs with vertices $1,2,\dots,n$.  $G$ is the start
state, and the final states are the graphs on which no operation is
possible.

\begin{problemparts}

\problempart\pts{4} Let $G$ be the graph with vertices $\set{1,2,3,4}$ and edges
\[
\set{\set{1,2},\set{3,4}}
\]
How many possible final states are reachable from start state
$G$? \hfill \brule{1in}

\solution{It's not possible to delete any edge.  The procedure can only
add an edge connecting exactly one of vertices 1 or 2 to exactly one of
vertices 3 or 4, and then terminate.  So there are four possible final
states}

\problempart\pts{8} \label{derived} On the line next to each of the derived
state variables below, indicate the \emph{strongest} property from the
list below that the variable is guaranteed to satisfy, no matter what the
starting graph $G$ is.  The properties are:
\begin{center}
\begin{tabular}{cccccc}
\emph{constant} & \emph{increasing} & \emph{decreasing} &
\emph{nonincreasing} & \emph{nondecreasing} & \emph{none of these}
\end{tabular}
\end{center}

For any state, let $e$ be the number of edges in it, and let $c$ be the
number of \textbf{connected components} it has.  Since $e$ may increase or
decrease in a transition, it does not have any of the first four
properties.  The derived variables are:
\begin{enumerate}

\item[0)] $e$ \hfill \underline{\emph{none of these}}


\item[i)] $c$ \hfill \brule{1.0in}

\solution{nonincreasing}

\item[ii)]  $c+e$ \hfill \brule{1.0in}

\solution{nonincreasing}

\item[iii)] $2c+e$ \hfill \brule{1.0in}

\solution{decreasing}

\item[iv)] $(c,e)$, under the \textbf{lexicographic order} on $\nats \cross \nats$.
\hfill \brule{1.0in}

\solution{decreasing}

\end{enumerate}

\problempart\pts{8} Explain why, starting from any state, $G$, the procedure
terminates.  If your explanation depends on answers you gave to part~(b),
you must justify those answers.

\solution{4 pts: The derived variable iii) is a natural-number valued
variable and is decreasing.  \emph{Alternative answer}: derived variable
iv) is decreasing under the lexicographic order on $\nat \cross \nats$
which we know from Problem Set 6 is a well-ordered set.

We saw in Notes \#6 that this means the procedure must terminate.

4pts: To show that the variable iii) decreases, note that the rule for
deleting an edge ensures that the connectedness relation does not change,
so neither does the number of connected components; therefore the variable
decreases by one when an edge is deleted.  The rule for adding an edge
ensures that the number of connected components decreases by one, so the
variable changes by $-2$ for the reduced number of components and $+1$ for
the added edge, for a net decrease of 1.  This also shows that variable
iv) decreases.}

\problempart\pts{10} Prove that any final state must be an \textbf{unordered
tree} on the set of vertices, \ie a spanning tree.

\solution{We use the characterization of a tree as a cycle-free,
connected, simple graph.

A final state must be connected, because otherwise there would be two
vertices with no path between them, and then a transition adding the edge
between them would be possible, contradicting finality of the state.

A final state can't have a cycle, because deleting any edge on the
cycle would be a possible transition.}

\end{problemparts}

\end{problem}
