\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\newcommand{\mod}{ \mbox { mod }}

\begin{document}

{\bf Tutorial 3 solutions. }

\date{}
\begin{theorem}
A graph $G$ is bipartite iff it has no odd cycles.
\end{theorem}
  
{\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

\begin{theorem}
A connected loopless undirected graph $G=(V,E)$ has an Euler tour
iff the degree of every vertex is even.
\end{theorem}

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


