\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{rec#1}{Notes for Recitation #1 (#2/98)}{#3}
}


\begin{document}

\recn{3}{2/20}{March 3, 1998, 7pm}

\section{Buildup Error}

``Buildup error'' is a common source of mistakes in inductive proofs.
We saw an example in lecture yesterday.  Let's look at another 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.


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


\section*{Team Problems}

\begin{problems}

\problem

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

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

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

\end{document}
