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

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{5}{March 16,1995}{In recitation, March 24}

\bigskip


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Let $G = (V,E)$ be an undirected graph.  Define the {\it line graph}
$G' = (E,E')$ as the graph whose vertices are the edges of $G$, and
$(e_1,e_2) \in E'$
 iff $e_1$ and $e_2$ share an endpoint in $G$.

Argue that if $G$ is Eulerian then so is $G'$. (Be sure to argue that if $G$
is connected then so is $G'$ as part of your proof).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Let $G_1=(V,E_1)$ and $G_2=(V,E_2)$ be two trees on the same set of
vertices.

Define the graph $G=(V,E)$ where $E=E_1\cup E_2$.
\bparts
\ppart
Prove that $G$ is 4-colorable.
\ppart
Give an example to show that the result cannot be improved. That is,
show
that there are 2 trees whose union is not 3-colorable.
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Prove that $\{\bar{\wedge}\}$ (NAND) defined by $A \, \bar{\wedge} \, B = \neg(A
\wedge B)$ is a complete basis but $\{\rightarrow\}$ is not.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

For $x$ and $y \in\{0,1\}^n$ we say that $x \leq y$ if $x_i \leq y_i$ for
all $i$.  A function $f : \{0,1\}^n \rightarrow \{0,1\}$ is {\it monotone} if $x
\leq y$ implies that $f(x) \leq f(y)$.  Another way of saying this is that
if $f(z) = 1$ then changing any bit that is $0$ in $z$ to $1$ should not
change the value of the function from $1$ to $0$.  

If $g : \{0,1\}^k \rightarrow
\{0,1\}$ and $f : \{0,1\}^n \rightarrow \{0,1\}$ are boolean functions we
define the composition of $f$ and $g$ as $(f \circ g) : \{0,1\}^{nk}
\rightarrow \{0,1\}$ where $(f \circ g)(x_1 x_2 \ldots x_n) =
f(g(x_1)g(x_2) \ldots g(x_n))$.

Prove that the conjunction, disjunction, and composition of monotone
functions are monotone.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Prove that $\{A \rightarrow (B \wedge D), B \rightarrow D\}  \vdash A \rightarrow
D$.


\end{problems}

\end{document}
