\documentstyle[12pt,twoside,amstex]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\newtheorem{falsethm}[theorem]{False Theorem}
%\newtheorem{fact}{Fact}
%\newtheorem{axiom}{Axiom}


\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{tut#1}{Notes for Recitation #1 (#2/98)}{#3}
}


\begin{document}

\recn{3}{2/25}{September 25, 1998}

\section{Buildup Error}

``Buildup error'' is a common source of mistakes in inductive proofs.
Let's look at an example.

\begin{quotation}
\noindent {\bf False Theorem}: If every vertex in a vertex-colored simple
graph is adjacent to a vertex of the same color, then the graph is
monochromatic.
\end{quotation}

{\bf Class exercise}.  Exhibit a simple counter-example to this claim.

{\bf Solution}: A cycle on four vertices with two red vertices followed by
two blue vertices.  Each vertex is adjacent to some vertex of the same
color, but the graph is not monochromatic.


\medskip
%(THIS IS PROOF IS PART OF THE TEAM PROBLEM HANDOUT.)

{\bf False Proof}: By induction on the number of vertices in the
graph.  Let $P(n)$ be the predicate, ``If every vertex in an $n$-vertex
vertex-colored simple graph is adjacent to a vertex of the same color,
then the graph is monochromatic.''

In the base case, $P(1)$, the graph contains only one vertex and so is
certainly monochromatic.

For the inductive step, we assume $P(n)$ in order to prove $P(n+1)$.  For
$n\geq 1$, let $G=(V,E)$ be a vertex-colored graph with $n+1$ vertices
such that every vertex is adjacent to a vertex of the same color, and let
$v \in V$ be an arbitrary vertex.  Let $G'$ be the subgraph of $G$
obtained by deleting $v$.  Since $G'$ is an $n$-vertex graph, we have by
induction that $G'$ is monochromatic.  By hypothesis, $v$ is adjacent to a
vertex $v'$ of the same color.  Since $v'$ must be a vertex of $G'$, it
follows that $v$ has the same color as all the other vertices.  Therefore,
$G$ is indeed monochromatic. \qed


{\bf Class Exercise}.  Pinpoint the flaw in this proof.

{\bf Solution}: the flaw is in the statement, ``Since $G'$ is an
$n$-vertex graph, we have by induction that $G'$ is monochromatic.''  This
is incorrect.  We can assume only that {\bf if} {\em every vertex in $G'$
is adjacent to a vertex of the same color}, {\bf then} we have by
induction that $G'$ is monochromatic.''  Unfortunately, removing $v$ from
$G$ may yield a $G'$ for which the adjacency condition fails.

\medskip
The correct assumption does not apply to $G'$ and does not lead to a
proof.  Of course a breakdown of the proof was inevitable, since the
theorem is false!

{\bf Class exercise}: Verify that the red/blue 4-cycle above is example
where the adjacency assumption fails for $G'$.

{\bf Solution}: We saw red/red/blue/blue 4-cycle satisfies the adjacency
condition.  Now remove, say, a red vertex.  Resulting graph red/blue/blue
graph leaves red vertex w/o a red neighbor.


\iffalse
\section{Well-Ordering}

There is another variation of induction that is sometimes useful:
well-ordering.  The well-ordering axiom looks nothing like the
induction axiom:

\begin{axiom}
Every nonempy set $S \subseteq \naturals$ has a smallest element.
\end{axiom}

The well-ordering axiom is often called the well-ordering
{\em principle}.  It may seem obvious and useless!

As for obvious, note that this axiom would be false if the set of
non-negative integers, $\naturals$, were replaced by, say, the set of
non-negative rational numbers; then for example the subset consisting of
the positive rational numbers has no smallest element.  It would also be
false if $\naturals$ was replaced by the set of {\em all} integers; then
the whole set has no least element.

As for useless, it may be surprising that everything that can be proven by
induction can also be proven using the well-ordering principle!  It's not
hard to prove this metamathetical fact, but we won't bother.  We'll just
illustrate a typical use of the Well-Ordering Principle.

Here is a special case of the {\em Principle of Inclusion-Exclusion}
which we'll take up in a few weeks.

\begin{theorem}
For all finite sets $A, B$
\[|A \cup B| = |A| + |B| - |A \cap B|. \]
\end{theorem}

Rosen, Section 1.5, Example 5 gives a simple explanation for this
equality: take the set $A \cup B$ and mark each element of $A$ and then
mark each element of $B$.  So the total number of marks is $|A|+|B|$.  The
elements in $A \cap B$ now wind up with two marks, while the others get
one mark.  If we now remove one mark from each element in $A \cap B$, we
are left with a total of $|A|+|B|- |A \cap B|$ marks.  Since each element
of $A\cup B$ is now left with exactly one mark, this last total must equal
$|A \cup B|$.

This is a pretty good argument which we would actuallly accept as a proof
later in the term---after we've had more experience recognizing when such
an argument can be reduced to careful reasoning about numbers, functions,
and sets.  But at this point in the term, the concepts of ``marking'' and
the rules for their bookkeeping remain too fuzzy for comfort.  So let's
prove the theorem with careful, elementary reasoning.

We'll need three simple facts relating set size to set operations in the
proof.
\begin{fact}
Any subset of a finite set is finite.
\end{fact}
\begin{fact}
$|A| = 0$ iff $A = \emptyset$.
\end{fact}
\begin{fact}
If $A$ is a finite set and $x \not \in A$, then $|A \cup \{x\}| = |A|
+ 1$.  In other words, if we add a new element to a set, it gets larger by
one.
\end{fact}
We could prove these three facts themselves from the definition of the
cardinality, $|A|$, of a finite set, $A$, using simple reasoning about
sets, but they are so simple and familiar that we'll take them for
granted.  (Definition 4 of Rosen, Section 1.4 claims to specify the
cardinality of a finite set, but it's not very crisp.  The precise
mathematical definition is that for $n \in \naturals, |A|$ is defined to
be $n$ iff there is a bijection from the integers $1,\dots, n$ to $A$.
And $A$ is {\em finite} iff $|A| = n$ for some $n \in \naturals$.)

{\em Proof by contradiction}: We will suppose the inclusion-exclusion
equality fails for some finite $A, B$ and reach a contradiction.

Suppose the equality fails for some finite $A, B$.  By Fact 1, $A - B$ is
also finite.  By the Well-Ordering Principle, there must therefore be
finite sets $A, B$ for which the equality fails and such that $|A - B|$ is
minimum among all such sets.

Note that by Fact 2, $|A - B| = 0$ iff $A - B = \emptyset$ iff $A
\subseteq B$.  But the inclusion-exclusion equality clearly holds when $A
\subseteq B$, so we conclude that $A - B \neq \emptyset$, that is, there
is some element $a \in A-B$.

Let $A' = A - \{a\}$.  From Fact 3
\[|A| = |A'| + 1.\]
Similarly, $A \cup B = (A' \cup B) \cup \{a\}$ and $a \not \in A' \cup B$,
so by Fact 3
\[|A \cup B| = |A' \cup B| + 1.\]
Likewise, $A - B = (A' - B) \cup \{a\}$ and $a \not \in A'-B$, so
\[|A - B| = |A' - B| + 1.\]
In particular, $|A' - B| < |A - B|$.  Finally, since $a \not \in B$, we
have that $A \cap B = A' \cap B$, so
\[|A \cap B| = |A' \cap B|.\]

Since $|A' - B| < |A - B|$ and $|A - B|$ was minimum for the equality to
fail, the equality must hold for $A', B$, that is,
\[|A' \cup B| = |A'| + |B| - |A' \cap B|. \]
Hence, 
\begin{eqnarray*}
|A \cup B| & = & |A' \cup B| +1\\
           & = & |A'| + |B| - |A' \cap B| +1\\
           & = & |A'| + 1 + |B| - |A \cap B|\\
           & = & |A| + |B| - |A \cap B|
\end{eqnarray*}
contradicting the fact that the equality fails for $A, B$. \qed

As we noted, Well-Ordering proofs can always be reformulated as proofs by
induction, and vice-versa.  In particular, the Well-Ordering proof above
can easily be transformed into a proof by induction on the size of $A-B$,
as the reader should check.

\fi

\section{Bipartite Graphs}

Recall that a graph is $k$-colorable if every vertex can be assigned
one of the $k$ colors so that no adjacent vertices have the same
color.  A 2-colorable graph is called {\em bipartite}.  Many common
types of graph are bipartite, and they often arise in computer
science.

\begin{theorem}
Every tree is bipartite.
\end{theorem}

Before proving this theorem, we'll first prove a lemma about trees.

\begin{lemma}
Every tree has a vertex of degree 1.
\end{lemma}

{\em Proof. } The proof is by contradiction.  Suppose that there is an
$n$-vertex tree that has no vertex of degree 1.  Since a tree is
connected, no vertex can have degree 0.  As a result, every vertex
must have degree at least 2.  Since the number of edges in a graph is
half the sum of the degrees, the number of edges must be at least
$\frac{1}{2} (2n) = n$.  This contradicts the fact that an $n$-vertex
tree has exactly $n-1$ edges.  \qed

Now we can use the lemma to prove the theorem that every tree is
bipartite.

{\em Proof. } The proof is by induction.  Let $P(n)$ be the predicate
that every tree with $n$ vertices is bipartite.  In the base case,
$P(1)$ is true because a graph consisting of a single vertex can be
colored with just one color.  In the inductive step, for $n \geq 1$
assume that every tree with $n$ vertices is bipartite in order to
prove that every tree with $n+1$ vertices is bipartite.

Let $G$ be a tree with $n+1$ vertices.  By the lemma, we can pull off
a vertex $v$ with degree 1.  The remaining $n$-node graph is a tree.
(The reason is that we removed one node and one edge and did not
introduce a cycle.  Therefore, the remaining graph is acyclic and has
$n$ nodes and $n-1$ edges.  This defines a tree.)  By induction, the
remaining graph is bipartite.  The extra vertex $v$ can take whatever
color that its single neighbor does not.  \qed


\section{Counting Graphs}

How many simple
graphs (up to isomorphism) are there with $|V| = |E| = 5$?
\medskip

{\bf Solution:}
If two graphs are isomorphic, then they have the same size maximum cycle.  This should
be clear.  If they don't, then there is no labelling of the vertices that will make
the two graphs identical, because one will have the cycle $V_1, V_2, V_3, \dots V_n$ and
the other will not have such a cycle.  So for this problem, one only needs to consider
the number of isomorphic graphs for each size of maximum cycle.  If the maximum cycle is
five, there is only one graph, and the entire graph is that cycle.  If the maximum cycle
is four, there are two graphs, one with one connected component, and one with two 
connect components.  Finally, if the maximum cycle is three, there are three graphs, 
depending on how the missing two vertices are connected to the 3-cycle.



\section{Posets and Hasse Diagrams}

The reflexivity, antisymmetry and transitivity properties are abstract
properties that generally describe ``ordering'' relationships. 
So often write an ordering-style symbol like $\preceq$ instead of just
a letter like $R$, for a p.o. relation. 
But this could be misleading -- note that $\geq$ is a p.o. on natural
numbers, as well as $\leq$.  If we use the $\preceq$ symbol for $\geq$,
things look really funny. 
(In cases like this, better to use $R$.)

A partial order is always defined on some set $A$.  The set together
with the partial order is called a ``poset'':
\begin{defin}
A set $A$ together with a partial order $\preceq$ is called a 
{\bf poset\/}  $(A, \preceq)$.
\end{defin}

Posets can usually be nicely drawn as a graph (Informally, dots and arrows.
That is, we draw an arrow from $a$ to $b$ if $a R b$. 
(Similar to what we've already done with relations.)

As an example, let us use a poset that describes the order in which one
would put on clothes (men only here).
The set is of clothes, and the partial order
specifies what should be put on before what.

\setlength{\unitlength}{0.012500in}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(220,75)(20,760)
\thinlines
\put(165,817){\vector( 0,-1){ 20}}
\put(240,817){\vector( 0,-1){ 20}}
\put(240,787){\vector( 0,-1){ 20}}
\put(165,787){\vector( 0,-1){ 20}}
\put( 25,797){\vector( 0,-1){ 25}}
\put( 85,797){\vector( 0,-1){ 25}}
\put(180,787){\vector( 3,-1){ 51}}
\put(178,765){\vector( 1, 0){ 53}}
\put(153,795){\vector(-4,-1){88}}
\put(155,790){\makebox(0.1111,0.7778){\SetFigFont{5}{6}{rm}.}}
\put(153,790){\vector(-2,-1){ 32}}
\put( 20,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}left sock}}}
\put( 20,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}left shoe}}}
\put( 80,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}right sock}}}
\put(235,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}shirt}}}
\put(155,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}underwear}}}
\put(235,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}tie}}}
\put(235,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}jacket}}}
\put(155,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}belt}}}
\put(155,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}pants}}}
\put( 80,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{rm}right shoe}}}
\end{picture}

Notice that some arrows are left out.  E.g., underwear precedes belt. 
But all those omitted follow from transitivity. 
Loops (which express reflexive relationships) also aren't shown.

\begin{defin}
A {\bf Hasse diagram\/} for a poset $(A,\preceq)$ is a graph:\\ 
- whose vertices are the elements of $A$, \\
- whose edges (arrows) represent pairs $(a,b)$, where $a \leq b$ but
$a \neq b$, \\
- that contains no ``transitive edges'', \\
- for which all pairs in $\preceq$ are obtainable by transitivity from
edges in the diagram.
\end{defin}

To convert the diagram above to an ``official form'' Hasse diagram,
must remove the pants $\rightarrow$ jacket arrow. 

Notice that the graph above has directed paths, that is,
sequences of nodes $a_1 \cdots a_n$ where $(\forall i<n) a_i R a_{i+1}$.
However, it does not have any directed cycles, a directed path where
$a_1 = a_n$. That is a good thing,
because otherwise we could get stuck trying
to get dressed.  This is true of all posets.

\subsection*{Partial vs. Total Orders}

A partial order is called {\em partial \/} because it is not necessary
that an ordering exist between every pair of elements in the set. 
For example, Lshoe and Rshoe have no prescribed ordering between them.

%E.g., For two sets, it's not necessary that either be a subset of the
%other. \\
%\\
When there is no prescribed order between two elements we say that they
are ``incomparable''. 

\begin{defin}
$a$ and $b$ are {\bf incomparable\/} if neither $a \preceq b$ nor $b
\preceq a$.
\end{defin}

\begin{defin}
$a$ and $b$ are {\bf comparable\/} if $a \preceq b$ or $b \preceq a$.
\end{defin}

For example, for subsets of $\naturals$, $\{ 1,2,3 \}$ and $\{ 2,3,4 \}$ are
incomparable. 

However, a partial order need not have incomparable elements. 
As a special case, we can have a p.o. in which there is a specified
order between every pair of elements.
Such partial orders are called ``total orders''.

\begin{defin}
A poset $(S, \preceq)$ is {\bf totally ordered\/} if 
$(\forall a,b \in S) [ a \preceq b \vee b \preceq a ]$.
\end{defin}

Examples:
\begin{itemize}
\item $S=\naturals, \preceq = \leq$
\item $S=\naturals, \preceq = |$, NOT because neither $3|5$ nor $5|3$
\item $S=P(\naturals), \preceq = \subseteq,$ NOT because neither $\{3\}
  \subseteq \{5\}$ nor $\{5\} \subseteq \{3\}$ (just said this above)
\item Lexicographic order on pairs of natural numbers, defined by:
$(a_1,a_2) \preceq (b_1,b_2)$ if and only if either $a_1 < b_1$, 
or else $a_1 = b_1$ and $a_2 \leq b_2$. \\
Do some examples here. $(2,37) \preceq (2,38) \preceq (3,2)$. \\
``Lexicographic'' because like dictionary.
\end{itemize}

The Hasse diagram of a total order looks like a line. 

%This has been the basic material. \\
%Book has a bit more: \\
%minimal, maximal elements (nothing smaller, nothing larger) \\
%lower bounds, upper bounds (for a subset -- $\leq$ everything in the
%subset, or $\geq$) \\
%lub, glb, \\
%lattices. \\
%I'll leave you to read these parts, do some for HW. \\
%\\
%Rest of the hour I'll cover some slightly more advanced material and
%some applications in c.s.

\subsection*{Topological Sorting}

Sometimes when we have a partial order,
e.g., of tasks to be performed,
we want to obtain a consistent total order,
e.g., an order in which to perform all the tasks, one at a time, so as
not to conflict with the precedence requirements. 

The task of finding an ordering that is consistent with a partial
order is known as ``topological sorting''.

\begin{defin}
A {\bf topological sort\/} of a finite poset $(A, \preceq)$ is a total
ordering of all the elements of $A$, $a_1, a_2, \cdots, a_n$ \\
in such a way that $\forall i < j$, either $a_i \preceq a_j$ or $a_i$
and $a_j$ are incomparable. 
\end{defin}

For example, underwear, shirt, Lsock, Rsock, pants, tie, Lshoe, Rshoe,
belt, jacket is a topological sort of how to put on a suit.
One of the nice facts about posets is that such an ordering always
exists and is even easy to find:

\begin{theorem}
Every finite poset has a topological sort.
\end{theorem}

We'll prove this by induction,
on the number of elements in the domain of the poset. 
The basic idea is to pick a ``smallest'' element to start and then
proceed recursively.

\begin{defin}
A {\bf minimal\/} element $a$ in a poset $(A, \preceq)$ is one for
which $(\forall b \in A) [ a \preceq b \vee a \mbox{ and } b \mbox{ are
incomparable }]$.
\end{defin}

Notice that there can be more than one minimal element. There are 4 in
the clothes example: Lsock, Rsock, underwear, shirt.

\begin{lemma}
Every finite poset $(A,\preceq)$ has a minimal element.
\end{lemma}

\begin{proof}
By contradiction. \\
Assume no minimal elements.
Then $(\forall a \in A) (\exists b \neq a) [ b \preceq a ]$. 

Start from any element of $a$ and construct a sequence of successively
smaller elements, by using the fact above.
At each step, can get another element preceding the most recent.
Can't repeat any of the previous ones in the chain, since that would
create a cycle (and we know a poset has no cycles). \\
So just keep going forever, creating an infinite chain of distinct
elements.

But this is nonsense, because $A$ is a finite set.
Contradiction, so there must be some minimal element.
\end{proof}

Now we can prove the existence of the topological sort.

\begin{proof}
By (ordinary) induction. \\
$P(n)$ = any poset with $n$ elements has a topological sort. 

Base case $(P(1))$: for a poset with one element the one element makes a
topological sort. \\

Inductive step: Assume $(P(n))$. Consider a poset of $n+1$ elements.
By lemma it has a minimal element $u$.
Consider the same relation on $A-\{u\}$.
It is easy to check that it is still reflexive, transitive, and
anti-symmetric.
So by the inductive hypothesis, $A-\{u\}$ has a topological sort.

We put $u$ first and now have a topological sort on the whole poset.
This is because according to def of topological sort $u$ can't be in
the wrong order w.r.t. any of the later elements.

Thus every poset has a topological sort, by induction.
\end{proof}

%In our dressing example, we can
%construct ordering by picking one at a time.
%In each case, look at the remaining p.o. for remaining elements.
%Lsock, shirt, tie, Rsock, underwear, pants, Lshoe, belt, jacket, Rshoe
%
%E.g., subsets of $\{ 1,2,3,4 \}$ \\
%Draw lattice. \\
%$\emptyset$ is the unique minimal element, then have choices, e.g., do: \\
%$\{ 1 \}$, $\{ 2 \}$, $\{ 1,2 \}$ \\
%$\{ 3 \}$, $\{ 1,3 \}$, $\{ 2,3 \}$, $\{ 1,2,3 \}$, \\
%$\{ 4 \}$, $\{ 1,4 \}$, $\{ 2,4 \}$, $\{ 3.4 \}$, \\
%$\{ 1,2,4 \}$, $\{ 1,3,4 \}$, $\{ 2,3,4 \}$, $\{ 1,2,3,4 \}$


\section*{Team Problems}

\begin{enumerate}

\item Prove that a graph is bipartite iff it does not contain an odd
cycle.

{\em Proof. }
\begin{enumerate}
\item   If $G$ is bipartite then it has no odd cycles.

Proof by contradiction.
Assume for the purpose of a contradiction that $G$ is bipartite and 
has an odd cycle, $C = v_1,v_2,..,v_{2k-1},v_1$.
Let $v_1$ be colored red. Then $v_2$ and $v_{2k-1}$ must be colored blue,
and then $v_3$ and $v_{2k-2}$ must be colored red and in general
for $1 < i \leq k$, $v_i$ and $v_{2k-i+1}$ must be the same color.
We prove this by induction on $i$.

{\em Ind. Hyp.} $P(i)$: In any two coloring of $C = v_1,v_2,..,v_{2k-1},v_1$, $v_i$ and $v_{2k-i+1}$ are the same color.

{\em Base.} $P(2)$. $v_2$ and $v_{2k-1}$ are adjacent to $v_1$, so they
must be colored differently from $v_1$, hence they get the same color.

{\em Step.} Assume $P(i)$. That is $v_i$ and $v_{2k-i+1}$ are the
same color, say red. Then $v_{i+1}$ must be blue and $v_{2k-i}$ must be 
blue also.

From $P(k)$ we have that $v_k$ and $v_{k-1}$ must be the same color which
is not allowed in a valid coloring.
But this implies that the vertices of $G$ cannot be colored with only
two colors. This is a contradiction since $G$ is bipartite and every 
bipartite graph can be colored with 2 colors.

\item If $G$ has no odd cycles then it is bipartite.

Each component of $G$ can be colored separately. So assume $G$ is
a connected graph. We will assign a {\em level} to every vertex of $G$.
Pick some vertex $w$ of $G$, place it at level 1. Then place all the
neighbors of $w$ at level 2. Now among the remaining vertices, 
place all those that are  neighbors of vertices
in level 2 at level 3 and so on. In general, level $i+1$ has the 
neighbors of vertices in level $i$ from the remaining graph.

Notice that each edge runs from some level to an adjacent level only,
i.e., an edge cannot jump across many levels.

Now to show $G$ is bipartite, we can color it as follows: give
the vertices in odd numbered levels the color red and the vertices
in even numbered levels the color blue.

Is this a valid coloring? Suppose not, i.e. there is some edge 
$(u,v)$ such that $u$ and $v$ are the same color. Then $u$ and $v$ 
must be on the same level $i$. Let $u,u_{i-1},u_{i-2},\ldots,w$ be
vertices on a shortest path from $u$ to the start vertex $w$. 
Similarly, let $v,v_{i-1},\ldots w$ be a shortest path from $v$ to $w$.
Let the first vertex where these paths meet be $u_k=v_k$. Then
$u_k,u_{k+1},\ldots,u,v,v_{i-1},\ldots,v_{k-1},v_k$ is a cycle of
odd length. Since we stopped at the first level where the paths had 
a common vertex, this must be a simple cycle: a vertex could not have
been repeated on either of the paths and there is only one vertex
that could have occured in both paths, namely the one where they first meet.
This is a contradiction since we assumed that $G$ has no odd cycles.
\end{enumerate}
\qed


\item An {\em Euler cycle} of a graph is a cycle that contains every
edge in the graph exactly once.  Prove that a connected graph without
self-loop edges has an
Euler cycle iff every vertex has even degree.

{\em Proof.} 
\begin{enumerate}
\item Assume $G$ has an Euler tour.  Direct the edges according 
to the tour, i.e. if on the tour we go from $u$ to $v$ then direct
the edge from $u$ to $v$. Since we leave each vertex as many times
as we enter it, the number of in-edges is equal to the number of 
out-edges at every vertex, so the degrees are all even.

\item Now assume the degree of every vertex is even in a connected
loopless graph. We will prove by contradiction that $G$ has an
Euler tour. For this let $C$ be maximum-length cycle (allowing repeated
nodes but not repeated edges) in the graph.  If C contains all the
edges in G, then it is an Euler tour.  Suppose not for a contradiction.
Then there is some edge $e$ that is not included. Since $G$ is connected, 
there is a path from $e$ that eventually reaches a node of $C$.  
This means that there is an edge $e'$ that is not
in $C$ which is incident to a node $v$ in $C$.  
Look at $G-C$ and start a path using $e'$. Such a path will eventually return
to the start node $v$. This is because whenever we enter a vertex other than
the start node, since the degree is even, there is some unused edge we can use
to leave the node. Let this cycle be $C'$. Then we can create a single cycle
from $C$ and $C'$: start at $v$, traverse $C$, then traverse $C'$.
But this is a contradiction as we assumed that $C$ is the longest cycle in $G$.

\end{enumerate}

\qed

\end{enumerate}


\iffalse
\begin{problems}

\problem
\problem

Let $A$ be the adjacency matrix for a digraph $G$ with $n$ vertices.  Note
that $A$ is a zero-one valued $n \times n$ matrix.  In this problem we use
the Boolean ``OR'' operation, $\vee$, instead of ``+'' when multiplying
zero-one valued matrices (this is called ``boolean'' matrix product).

\bparts

\ppart

For $k \in \naturals$, let $A^k$ be the $k$th {\em Boolean} power
of $A$.  Prove that ${A^k}_{ij} = 1$ iff there is a directed path of
length $k$ from the $i$th to the $j$th vertices of $G$.

{\bf Solution:}

{\bf Proof:} by induction on k.\\

{\bf Inductive Hypothesis:} $P(k): {A^k}_{ij} = 1$ iff there is a directed path of
length $k$ from the $i$th to the $j$th vertices of $G$.\\

{\bf Base Case:} $k = 1$.  By the definition of an adjacent matrix A, 
$A_{ij} = 1$ iff there is a directed edge (directed path of length $k = 1$) from 
the $i$th to the $j$th vertices of $G$.\\

{\bf Inductive Step:} Assume $P(k)$ to prove $P(k+1)$.\\
\[{A^k}_{ij} = \bigvee_{l \in G} ({A^k}_{il} \wedge A_{lj})\]\\
Now we consider both directions for the iff.\\
Case 1: There is a directed path of length $k+1$ from the $i$th to the $j$th vertices of
$G$.\\
This path looks like $i, i_1, i_2, \dots i_k, j$.
Then consider $l = i_k$.
${A^k}_{il} = 1$ (inductive hypothesis).
${A}_{lj} = 1$ (there is an edge from $i_k$ to $j$), under the Case 1 assumption.  Therefore\\
\[({A^k}_{il} \wedge A_{lj}) = 1\]
\[{A^k}_{ij} = 1\]

Case 2: ${A^{k+1}}_{ij} = 1$.\\
Then $\exists l \in G : ({A^k}_{il} \wedge A_{lj}) = 1$.  Thus there is an edge from 
$l$ to $j$ and there is path of length $k$ from $i$ to $l$(by the inductive hypothesis)
which looks like $i, i_1, i_2, \dots i_{k-1}, l$.
Thus, there is a path of length $k+1$ from $i$ to $j$ which hits $l$ on the $k$th step
and then has the $k+1$st edge from $l$ to $j$.  This path follows the vertices:
$i, i_1, i_2, \dots i_{k-1}, l, j$.\\

Q.E.D.\\

\ppart

Let $B = A \vee I$ where $I$ is the $n \times n$ identity matrix.  Prove
that ${B^k}_{ij} = 1$ iff there is a directed path of length $\leq k$ from
the $i$th to the $j$th vertices of $G$.

{\bf Solution:}
From part a, it can be seen that ${B^k}_{ij} = 1$ iff there is a directed path
of length $k$ from the $i$th to the $j$th vertices of $G'$, where $G'$ is the
graph described by the adjacency matrix $B$.  Since $G'$ is just $G$ with self loops,
a path exists between $i$ and $j$ in $G'$ iff a path exists between $i$ and $j$ in 
$G$ (all vertices have paths of length $0$ to themselves).

For any such path between
$i$ and $j$ in $G'$, either it uses a self-loop edge or it does not.  If it does not,
then the equivalent path in $G$ will have the same length.  If it does, then there 
is a shorter path in $G$ which can be obtained by not using the self loop.
So if there is a path of length $k$ between $i$ and $j$ in $G'$ then there is a path of
length $\leq k$ between $i$ and $j$ in $G$.

If there is a path of length $\leq k$ between $i$ and $j$ in $G$, then it can be made
to be of length $k$ by using self loops to lengthen the path.  Thus there is a path in
$G'$ of length $k$ iff there is a path in $G$ of length $\leq k$.  Since
${B^k}_{ij} = 1$ iff there is a path of length $k$ between $i$ and $j$ in $G'$ then ${B^k}_{ij} = 1$ iff
there is a path of length $\leq k$ between $i$ and $j$ in $G$.\\

\ppart 

Conclude that ${B^n}_{ij} = 1$ iff there is a directed path from the $i$th
to the $j$th vertex.

{\bf Solution:}
If ${B^n}_{ij} = 1$ then there is a directed path from the $i$th to
the $j$th vertex.  If ${B^n}_{ij} = 0$ then there is no path of length
$<=n$ from the $i$th to the $j$th vertex.  There must also be no path of
length $>n$ from the $i$th to the $j$th vertex.  If there were, then the
path must cross through some vertices twice, since the length of the path is
$>n$.  For those vertices through which the path passes twice, eliminate
the loops so that the path uses no vertex more than once.  This means the
path must be of length $<=n$, which reaches a contradiction, since we know
that there are no paths from $i$ to $j$ of length $<=n$.  Therefore, if
${B^n}_{ij} = 0$ there is no path from $i$ to $j$ at all.\\

\eparts


\problem

The {\em complement}, $\overline G$, of a simple graph, $G$, is defined to
be the graph which has the same vertices as $G$ such that two vertices are
adjacent in $\overline G$ if and only if they are not adjacent in $G$.

\bparts

\ppart A subset, $A$, of the vertices of a simple graph, $G$, such that no
two vertices in $A$ are adjacent in $G$, is called an {\em anti-clique} of
$G$.  Prove that $G$ contains an anti-clique of size $m$ iff $\overline G$
contains a copy of $K_m$.\\

{\bf Solution:}
Both directions must be proven.  Suppose $G$ contains an anti-clique $A$ of size $m$.
Then $\forall a \in A \forall b \in A (a \not = b) : ((a,b) \not \in G)$.  Therefore
$\forall a \in A \forall b \in A (a \not =  b) : ((a,b) \in \overline G$, so $\overline
G$ contains a copy of $K_m$.  \\

Suppose $\overline G$ contains a copy of $K_m$ called $A$. Then
$\forall a \in A \forall b \in A (a \not = b): ((a,b) \in \overline G)$.  Therefore
$\forall a \in A \forall b \in A (a \not = b): ((a,b) \not \in G)$.  Therefore
$G$ contains an anti-clique of size $m$.\\

\ppart

A simple graph, $G$, is called {\em self-complementary} iff $G$ and
$\overline G$ are isomorphic.  Prove that if $G$ is a self-complementary
simple graph with $n$ vertices, then
\[n \equiv 0 \pmod{4}\mbox{   or   }n \equiv 1 \pmod{4}.\]
\hint How many edges altogether are there in $G$ and $\overline G$?\\

{\bf Solution:}
The sets of edges for $G$ and $\overline G$ are disjoint and together make up all edges
in the complete graph $K_n$.  $K_n$ contains ${n(n-1)}/2$ edges.  Since $G$ and
$\overline G$ are isomorphic, they have the same number of edges, namely
${n(n-1)}/4$.  Since this number must be an integer, either $4|n$ or $4|(n-1)$.
So $n \equiv 0 \pmod{4}$ or $n \equiv 1 \pmod{4}$.\\

\ppart

For integer $n>0$, define a simple graph $G_n$ as follows: the vertices
are the integers $1,2,\dots,2n$.  Vertices $i \neq j$ are adjacent iff
$i,j \leq n$ or $(i \leq n \mbox{ and } j > n \mbox{ and } i \equiv j
\pmod{2})$.  

Prove that $G_n$ is not $(n-1)$-colorable.

{\bf Solution:}
Since all vertices $\leq n$ are adjacent to each other, $G_n$ contains $K_n$.
$K_n$ requires $n$ colors to color, so $G_n$ is not $(n-1)$-colorable.\\

\ppart

Prove that $G_n$ is self-complementary.

{\bf Solution:}
The graphs are isomorphic.  Consider the labelling of $G_n$.  Then label $\overline G_n$
such that for a particular vertex $i \in G_n$, it's number in $\overline G_n$ is
$2n+1-i$.  Vertices are adjacent in $G_n$ iff $i,j \leq n$ or $i\leq n$ and $j > n$ and
$i \equiv j \pmod{2}$.  Therefore, vertices in $G_n$ are not adjacent iff
$i,j > n$ or $i \leq n, j > n$ and $i \equiv j + 1 \pmod{2}$.  Thus, in $\overline G_n$,
vertices are adjacent iff $i,j > n$ or $i \leq n, j > n$ and $i \equiv j + 1 \pmod{2}$.
Under the isomorphism labelling for $\overline G_n$, this is equivalent to saying that
vertices are adjacent iff $(2n+1-i),(2n+1-j) \leq n$ or $(2n + j - 1) \leq n,
(2n+i-1) > n$ and $(2n+j-1) \equiv (2n+i-1) \pmod{2}$.  We want to show that
vertices in $\overline G_n$ are adjacent iff their partners in $G_n$ are
adjacent.  By the labelling, the statement $(2n+1-i),(2n+1-j) \leq n$ or 
$(2n + j - 1) \leq n, (2n+i-1) > n$ and $(2n+j-1) \equiv (2n+i-1) \pmod{2}$ is
the same statement as $i,j \leq n$ or $j \leq n, i > n$ and $j \equiv i \pmod{2}$.  So vertices in $\overline G_n$ are adjacent iff their partners in 
$G_n$ are adjacent.  Since this shows that the 
labelling results in identical graphs, $G_n$ and $\overline G_n$ are isomorphic, so
$G_n$ is self-complementary.\\

\eparts


\problem Let $G$ be a simple graph with $n>0$ vertices.  Prove that if $G$
has no vertex of degree $\geq m$, then $G$ has an anti-clique of size
$\geq n/m$.

\medskip
{\em Solution}: By strong induction on the number of vertices of $G$.

The base case $n \leq m$ follows by choosing the anti-clique to consist of
a single vertex.

So for the induction case, suppose $n > m$.  Pick any vertex of, $v$, of
$G$.  Remove $v$ and all vertices adjacent to $v$ from $G$; call the
remaining graph, $H$.  Now $H$ has at least $n - m$ vertices because $v$
has degree $< m$, and by definition of $H$, none of the vertices in $H$
are adjacent (in $G$) to $v$.  Since removing vertices does not increase
degrees, $H$ also has no vertex of degree $\geq m$.  By strong induction,
there is an anti-clique $A$ of $H$ of size at least $(n-m)/m = n/m - 1$.
So $A \cup \{v\}$ is an anti-clique of $G$ of size at least $n/m$. \qed


\bigskip
THE FOLLOWING PROBLEM WAS NOT USED.  IT'S MORE SUITABLE FOR LECTURE OR PSET
PRESENTATION.

\problem We have seen that both a graph and its complement may require a
lot of colors.  (In fact $G_n$ and hence $\overline G_n$ each contain a
copy of $K_n$, so neither is $(n-1)$-colorable.)

Is it possible to have a large graph such that {\em both} it and its
complement do {\em not} require a lot of colors?  A famous theorem of
Ramsey implies that this cannot happen---either the graph or its
complement must require a lot of colors.  More precisely,
\begin{quotation}

\noindent {\bf Theorem (Ramsey)}: Let $m$ and $l$ be positive integers,
and $G$ be a simple graph.  If $G$ has $\geq m^{l}$ vertices, then either
$G$ contains a copy of $K_l$ (and hence $G$ is not $l$ colorable) or
$\overline G$ contains $K_m$ (and hence $\overline G$ is not $m$
colorable).

\end{quotation}

Prove the Theorem.  \hint Induction on $l$.  There are two cases, (1) when
every vertex of $G$ has degree $< m^l$, or (2) when some vertex does have
degree $\geq m^l$.  The Lemma above handles case (1).

{\em Solution}:

The base case $l=1$ follows because $m^1 \geq 1$, and every graph with at
least one vertex has $K_1$ as a subgraph.

So assume that $G$ has at least $m^{l+1}$ vertices.  There are two cases:

(1) Every vertex of $G$ has degree $< m^l$.  Then by the Lemma, $G$ has an
anti-clique of size at least $m^{l+1}/m^l = m$, so $\overline G$ contains
$K_m$. \qed

(2) Some vertex, $v$, of $G$ has degree $> m^l$.  Let $H$ be the subgraph
obtained by restricting $G$ to the vertices adjacent to (and not
including) $v$.  Now $H$ has $\geq m^l$ vertices, so by induction,
either $H$ contains $K_l$ or $\overline H$ contains $K_m$.

Note that $\overline H$ is the restriction of $\overline G$ to the
vertices in $H$.  So if $\overline H$ contains a copy of $K_m$, so does
$\overline G$, and the Theorem holds.  Otherwise, $H$ contains a subgraph,
$C$, which is a copy of $K_l$.  So $C \cup \{v\}$ is the required copy of
$K_{l+1}$ in $G$. \qed

\end{problems}
\fi

\end{document}
