\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{axiom}{Axiom}
\newtheorem{fact}{Fact}

\begin{document}

\handout{recprobs3}{Problems for Recitation 3}{February 20, 1998}

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

 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


\begin{problems}

\problem

Pinpoint the flaw in this proof.


\problem

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


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

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

\ppart 

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

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

\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$?

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

\ppart

Prove that $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$.

\end{problems}
\end{document}
