\documentstyle[12pt,amstex,twoside]{article}
\input{macros-course}

\begin{document}
\psol{8}{April 3, 1997}

\begin{problems}


\problem
What is wrong with the following ``theorem'' and ``proof?''\\
{\em False theorem:} If every vertex in a graph has degree at least one then the graph is connected.\\
{\em False proof:} We prove the result by induction on the number of vertices. Let $P(n)$ be ``if every vertex in a graph with $n$ vertices has degree at least one then the graph is connected.''\\
Base case. $P(2)$ is true since the only graph satisfying the assumption is that with two vertices and one edge between them which is easily seen to be connected.\\
Inductive step. Assume $P(n)$ is true. Now, take any graph with $n$
vertices with minimum degree at least one and add a new vertex to
it. By inductive hypothesis the graph on $n$ vertices is
connected. Since the new vertex satisfies the assumption it must have
degree at least one, so it must have an edge connecting it to one of
the remaining $n$ vertices. Thus the whole graph is connected. Hence
$P(n+1)$ is true. Thus, $P(n)$ is true for all $n$.  

The ``theorem'' is in fact incorrect; consider the graph on vertices
$ab,c$ and $d$, with edges $(a,b)$ and $(c,d)$.
This problem was supposed to show an example of the dangers of
``build-up'' error.

The base case is fine --- $P(2)$ really is true.

The trouble with the proof is our ``build-up'' step in the
induction, where we form an $(n+1)$-node graph by attaching 
a vertex to an $n$-node graph of minimum degree at least one.  This does
{\em not} produce all possible $(n+1)$-node graphs of minimum degree 
at least one,
and so the set of graphs for which we end up proving the theorem is
{\em not} the set of all graphs of minimum degree at least one.

For example, the following graph is not produced by this ``building-up''
process: vertices $A,B,C,D$, and two edges $(A,B)$ and $(C,D)$.
(To see this, ask yourself how you could get this from a $3$-node
graph of minimum degree one --- the answer is that you can't.)

When doing an inductive proof about instances of size $n+1$, you need
to {\em start} with the size $n+1$ instance and argue that it can be
{\em reduced} to a size $n$ instance.  



\problem Prove that a graph contains an odd-length circuit if and only
if it contains an odd length cycle (hint: consider the shortest odd
length circuit).

Suppose the graph has an odd length circuit.  Consider the shortest
one $v_1,\ldots,v_k$ where $k$ is odd.  If it is a cycle, we are
done.   Otherwise, we must have $v_i = v_j$ for some $i \ne j$.
Assume without loss of generality that $i \ne j$.  Then our circuit
is actually made up of two smaller circuite.  The first is
$v_i,\ldots,v_{j-1}$ (since $v_{j-1}$ is connected to $v_j=v_i$) the
second if $v_j,\ldots,v_n,v_1,\ldots,v_{i-1}$ (since $v_{i-1}$ is
connected to $v_i=v_j$).   Note that these two ``subcircuits''
have lengths whose sum is the length of the original circuit, and thus
odd.  Since the sum of two even number is even, it must be the case
that one of the subcircuit lengths is odd.  But this contradicts our
choice of the smallest circuit.


\problem Prove that if $G$ is bipartite then it contains no circuits
 of odd length.

We prove the contrapositive.  Suppose $G$ has a circuit
$v_1,\ldots,v_k$ of odd length (so $k$ is odd).  Suppose $G$ is
bipartite---this means that the vertices can be colored ``red'' and
``blue'' such that no edge connects to vertices of the same color.
Suppose vertex $v_1$ is red (we can swap colors to make this so).
We claim that vertex $v_j$ is red if and only if $j$ is odd.  This
leads to a contradiction, since this implies that $k$ is red, but
$(v_k,v_1)$ is an edge in $G$.

To prove the claim we use induction on $j$.  $v_1$ is red by
assumption. Suppose $v_j$ is red if and only if $j$ is odd.  Then
(since there is an edge $(v_j,v_{j-1})$) it must be that $v_{j+1}$ is blue
if and only if $j$ is odd.  Rewriting, we have that $v_{j+1}$ is red
if and only if $j$ is even, which occurs if and only if $j+1$ is odd.


\problem Suppose $G$ is a connected graph with no odd cycles (or
circuits).  Fix a particular vertex $u$.  
\begin{problemparts}
  \problempart Prove that for any vertex $v$, the length of every path
  from $u$ to $v$ is odd or the length of every path from $u$ to $v$
  is even.

Suppose this is not true.  Then for some $v$ and $u$, there is an odd-length
path from $u$ to $v$ and an even length path from $u$ to $v$.  If we
connect these two paths, we get a circuit whose length is the sum of the
path lengths and thus odd.  It follows that $G$ has an odd-length
circuit which implies (from above) that it has an odd cycle, a contradiction.

  \problempart Suppose I color a vertex accoring to the odd/evenness of its
  paths from $u$.  Prove this is a legal coloring.  Deduce that $G$ is
  bipartite.

Suppose every vertex on an even-length path from $u$ is red while
every vertex on an odd-length path from $u$ is blue.  Note that this
is a well-defined coloring since every vertex is on only odd or only
even paths by the previous part.  Suppose for the sake of
contradiction that there is an edge $(v,w)$ with both endpoints the
same color, say red.   Then there is an even path from $u$ to $v$ and
and even path from $w$ to $u$.  Then the circuit formed by taking the
path from $u$ to $v$, the edge from $v$ to $w$, and the path from $w$
to $u$ has odd length, a contradiction.

\end{problemparts}

\end{problems}
\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
