From: "F. Tom Leighton" <ftl@math.mit.edu>
Message-Id: <199709190152.VAA03053@dedekind.mit.edu>
Subject: Re: Tutorial 3 solutions
To: vempala@math.mit.edu (Santosh Vempala)
Date: Thu, 18 Sep 1997 21:52:48 -0400 (EDT)
Cc: 6042-staff@theory.lcs.mit.edu
In-Reply-To: <199709182232.SAA29633@schauder.mit.edu> from "Santosh Vempala" at Sep 18, 97 06:32:56 pm
Content-Type: text
Status: R

Here are some corrections to make:

In the first problem, we should state which direction we are proving
first.  We should also state that we are using a proof by
contradiction or a proof by contrapositive--whichever you are doing.
But most important, the end of the proof is missing.  We need to argue
that one node received 2 colors or that the last node is adjacent to
nodes of 2 different colors.  The punchline is missing!

The second direction has a nasty bug.  The cycle must be simple
(otherwise a tree would not be acyclic--this point needs to be made
clear!!!)  The proof given does not show the cycle is simple.  

Also, the following argument might be better: Pick a node w.  For any
node v, define f(v) to be the length of the shortest path to w.  Color
v red if f(v) is even.  Otherwise, color v blue.  Now look at any edge
connecting u to v.  First argue that f(u) and f(v) can differ by at
most 1 since otherwise, we could find a shorter path for the node with
the bigger f value.  (Spell this out.)  If they differ by 1, we are
done since the nodes will have different color.  The last case is that
the nodes have the same f value.  This means that there is a closed
walk of length 2f(v)+1, which is odd.

Next we need to show that there is therefor an odd-length SIMPLE
cycle.  Details are still needed here.  I would try using well
ordering.  Look at the smallest odd-length closed walk.  If it is
simple, we are done.  If not, some node is used twice.  Look at such a
node and take the two consecutive times that it is used.  By splicing
here,we decompose the closed walk into 2 closed walks of less length.
One of them has odd length and we are done.

In Problem 2, there is another bug.  C might not meet all the H_i,
even if G is connected.  Try following the approach I outlined in the
correction to SS3.

Graphs are tricky things.  We really need to check these things and each
other very carefully.

Thanks, Tom


> 
> 
> Hi, here's a draft. Watch for corrections/changes from Tom/Eric.
> 
> Really sorry about today's lecture. Shouldn't have happened!
> santosh
> 
> 
> 
> \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.
> 
> Assume $G$ 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.
> 
> Hence $G$ is not bipartite if it has an odd cycle. In other words,
> if it is bipartite, it has no odd cycles.
> 
> \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 path from $u$ to the start vertex $w$. 
> Similarly, let $v,v_{i-1},\ldots w$ be a path from $v$ to $w$.
> xLet 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.
> 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 strong induction on the number of edges
> that $G$ has an Euler tour.
> 
> {\em Ind. Hyp. } $P(m)$: A connected loopless graph with even degrees and
> $m$ edges has an Euler tour.
> 
> {\em Base. } $m=0$. Single vertex.
> 
> {\em Ind. Step. } Assume $P(k)$ holds for all $k \leq m$.
> Consider a graph $G$ with $m+1$ edges. 
> 
> First, we'll find a cycle in $G$. For this start at some vertex,
> follow some edge to an adjacent vertex, choose some new edge of that
> vertex and repeat this (without using any edge a second time).
> Since the degrees are even whenever we enter a vertex there is some edge
> we can use to leave it. Do this till we see some vertex $v$ for the
> second time. When we see a vertex for a second time, let $C$ be the
> cycle consisting of edges we see from the first visit to $v$ till the 
> second visit. 
> 
> Consider $G-C$, i.e. the graph obtained on removing the edges of $C$ from
> $G$. All the vertices of $G-C$ have even degrees.  Consider the 
> connected components of $G-C$. Let them be $H_1,\ldots,H_k$ ($k$ might be 1).
> Each $H_i$ has fewer than $m$ edges. So we can apply the
> Ind. Hyp. and conclude that each $H_i$ has an Euler tour $E_i$.
> 
> We will put together the tours $E_1,..,E_k$ along with $C$ to
> get a tour of $G$. 
> Order the vertices of $C$ and walk along the edges of $C$. Whenever
> we reach a vertex $v$ that is in some $H_i$ (it could be in more than one 
> $H_i$), take the tour of the $H_i$ and then continue on $C$ till we 
> we get back to the vertex we started at on $C$. (draw figure in class..)
> Every edge is visited exactly once. 
> \end{enumerate}
> 
> \qed
> 
> 
> 
> 
> \end{document}
> 
> 
>