\documentstyle[12pt,twoside,macpsfig]{article}
\input{macros-course}

\begin{document}

\handout{ps2}{Problem Set 2}{February 8, 1994}
\pset{2}
{\bf Reading:\ } Cormen, Leiserson \& Rivest: Chapter 5 (Handout 9). 
Maurer \& Ralston: Section 0.1--3, Chapter 2, Sections 3.1--3.

\medskip

The Athena course locker containing course handouts has been set up.
Type {\tt attach 6.042} at the Athena prompt and then {\tt cd
/mit/6.042} to get into the course directory.  Once there, you can
type {\tt lpr -P$\ang{\mbox{printer-name}}\
\ang{\mbox{file-name}}$} to print the file of your choice.  For example, to
print this handout you would type {\tt lpr
-P$\ang{\mbox{printer-name}}$ H07-Pset2.ps}.

\medskip

The problems are divided into oral problems (prefix~``{\bf O}'') and
written problems (prefix~``{\bf W}'').
The oral problems are due in tutorial on Monday, February 14.  
The written problems are due at the beginning of class on Tuesday,
February 15.  Remember to write up each problem on a separate page or
pages, with your name on each sheet.  Read
Handout~\ref{course-information} for the policy on problem sets.

\medskip


\medskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Let $G=(V,E)$ be an undirected graph, and let $r:V\to\reals$
be a function associating a real number with each vertex.  Suppose $r$
satisfies the property that for each $v\in V$, the value $r(v)$ is the
average of the values of $v$'s neighbors.  Prove that if the graph is
connected, then $r(u)=r(v)$ for all $u,v\in V$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Let $G=(V,E)$ be an $n$-vertex dag (directed acyclic graph).
Show that each vertex $v\in V$ can be assigned a distinct number
$r(v)$ from the set $\set{1,2,\ldots,n}$ such that if $(u,v)\in E$,
then $r(u)<r(v)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Prove that in any set of $101$ distinct integers chosen from
$\set{1,2,\ldots,200}$, there exist two such that one is an integer
multiple of the other.  Produce a set of $100$ distinct integers in
$\set{1,2,\ldots,200}$ such that no number in this set divides
another.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Prove that the number of leaves in any rooted binary tree is
one more than the number of nodes with degree~$2$.  (Read the footnote
concerning the degree of a node in a rooted tree on page 94 of
Handout~9.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Prove that edges of any connected, undirected graph with an
even number of edges can be oriented so that every vertex has even
out-degree.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Verify or falsify the following proof that a binary relation
$R$ that is symmetric and transitive is also reflexive, and hence, an
equivalence relation.  We have $aRb \Rightarrow bRa$ by symmetry, and
thus, by transitivity, it follows that $aRa$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Let $S$ be a finite set, and let $R$ be an equivalence
relation on $S\times S$.  Show that if $R$ is antisymmetric, then the
equivalence classes of $S$ with respect to $R$ are singletons.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Prove that any graph on $6$ vertices contains $3$ vertices
with no edges between them or $3$ vertices with all edges between
them.

%%	Ramsey Theorem:
%%  	A good written problem would be to prove Ramsey's general theorem
%% 	that for any (k,l), there is some n s.t. any graph on n nodes has
%%	either a k-clique or an l-ind.set.
%%	Do this by induction--assume true for (k-1,l) and (k,l-1).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Prove that each vertex of an undirected graph can be colored
red or grey such that every vertex is connected to at least as many
neighbors of the opposite color as it is to neighbors that are the
same color as itself.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \oproblem A full binary tree is a binary tree such that any node has
% either 0 or 2 children.  Prove that the number of internal nodes in a
% full binary tree is one less than the number of leaves.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\wproblem Each vertex of an undirected graph $G=(V,E)$ contains a
toggle switch and a lightbulb.  If you push the toggle switch in a
vertex, the bulb in the vertex goes off if it was on, and on if it was
off.  Moreover, all the bulbs in neighboring vertices are toggled as
well.

Initially, all the bulbs are off.  Notice that pushing the same switch
twice doesn't affect any of the bulbs.  Hence, we can talk of a
``setting'' of the switches, which corresponds to the subset of
vertices whose switches have been pushed once (or an odd number of
times).  The aim of this problem is to prove that for any undirected
graph $G$, there exists a \defi{good} setting of the switches: a
setting such that all the bulbs are turned on simultaneously.

\begin{problemparts}

\problempart Suppose that $G$ has an even number $\card{V}$ of
vertices.  Prove that if every graph on $\card{V}-1$ vertices has a
good setting, then a good setting for $G$ can be obtained by combining
(in some suitable way, which you have to come up with) the settings
corresponding to the subgraphs induced (see Handout 9, page 88) by the
$\card{V}$ subsets of $V$ that have $\card{V}-1$ vertices.

\problempart Suppose that $G$ has an odd number of vertices.  Prove
that there exists a vertex with even degree.

\problempart Suppose that $G$ has an odd number of vertices, let $v$
be an even-degree vertex, and let $S$ be the set of vertices that
includes $v$ and its neighbors.  Prove that if every graph on
$\card{V}-1$ vertices has a good setting, then a good setting for $G$
can be obtained by combining the settings corresponding to the
subgraphs induced by some $\card{V}-\card{S}$ subsets of $V$ that have
$\card{V}-1$ vertices.

\problempart Conclude that a good setting exists for any undirected
graph.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\wproblem A \defi{hamiltonian path} in an undirected graph is a simple
path that visits all the vertices.  An undirected graph is said to be
\defi{hamiltonian} if there exists a simple cycle that contains all
the vertices.  Let $A$ be the adjacency matrix of an undirected
graph~$G$, where we assume $A[v,v]=1$ for all $v\in V$.  The
\defi{cube} of $G$ is the graph $G^3=(V,E^3)$ whose adjacency matrix
is $A^3$, where we perform matrix multiplication using the boolean
operations $\vee$ and $\wedge$ instead of the usual $+$ and $\times$.
The aim of this problem is to show that the cube of any connected
graph is hamiltonian.

\begin{problemparts}

\problempart Prove that any connected graph contains a free tree that
connects all the vertices as a subgraph.

\problempart Argue briefly that $(u,v)\in E^3$, or equivalently, that
$A^3[u,v]=1$, if and only if the distance between $u$ and $v$ in $G$
is at most~$3$.

\problempart Prove by induction that the cube of any rooted tree
contains a hamiltonian path that begins at the root and ends at one of
its children.

\problempart Prove that the cube of any free tree is Hamiltonian, and
conclude that the cube of any connected graph is Hamiltonian.

\end{problemparts}

\end{problems}

\end{document}


