\documentstyle[12pt,twoside,expsfig,amssymb]{article}
\input{macros-course}
\input{LectureNotes/mk-macros}

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

\begin{document}

\psol{5}{March 24, 1995}

\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 a vertex in $G$.

\thm
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).
\ethm

\begin{proof}
We first show that if $G$ is connected then so is $G'$. 
Pick any two vertices $e_s, e_t$ of $G'$.
Let $e_s = (u,v), e_t = (x,y)$ in $G$, where
$u,v,x,y \in V$.  Since $G$ is connected, there is a path from $u$ to $x$.
Let the path be $u \equiv v_0 \rightarrow v_1 \rightarrow v_2 \cdots 
\rightarrow v_{k-1} \rightarrow x \equiv v_k$.
Edges on the path are $e_{i_1}e_{i_2} \cdots e_{i_k}$ where
$e_{i_j} = (v_{j-1}, v_{j})$, $j=1,2, \cdots k$. Then $e_s \equiv e_{i_0}
\rightarrow e_{i_1} \rightarrow e_{i_2} \cdots \rightarrow e_{i_k} 
\rightarrow e_{i_{k+1}} \equiv e_t$ is a path from $e_s$ to $e_t$ in $G'$, 
since for $0 \leq j \leq k$, edge $e_{i_j}$ and $e_{i_{j+1}}$ share an 
endpoint $v_j$. 

We next show that if all vertices in $G$ have even degree then so does 
each vertex of $G'$.
Take any vertex $e$ of $G'$. Let $e=(u,v)$. Define $N(i)=$ set of
neighbors of vertex $i$, and $d(i)=|N(i)|$ is the degree of
node $i$. If $e_i \in 
N(e)$ in graph $G'$, then $e_i$ and $e$ share an endpoint in $G$. That is,
$e_i=(u,w)$ or $e_i=(v,w)$, $w \in N(u) \cup N(v)$, where $w \neq u$ or $v$. 
So $d(e) = |N(e)| = |N(u)| + |N(v)| -2 = d(u) + d(v) -2$ is even,
if $d(u), d(v)$ are even. 

Finally, if $G$ is Eulerian, then $G$ is connected and has only even
degree vertices, therefore $G'$ is connected and has only even
degree vertices. Therefore $G'$ is Eulerian.
\end{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$.

\thm
$G$ is 4-colorable.
\ethm

\begin{proof}
First $2$-color $G_1$ and $G_2$ seperately. This is possible since we 
know that all trees are $2$-colorable.  Then for any vertex $v \in V$, 
color it $(c_1, c_2)$ in graph $G$ if it is colored $c_1$ in $G_1$ 
and $c_2$ in $G_2$.  Clearly, $(c_1, c_2)$ is of size $2 
\times 2 = 4$. Now prove that this is a legal coloring.
For any edge $(u,v) \in E$, say we get color $(c_1, c_2)$ and $(c'_1,
c'_2)$ by the above scheme.  Since $E=E_1\cup E_2$, we have either $(u,v)
 \in E_1$ or $(u,v) \in E_2$.  WLOG, say
$(u,v) \in E_1$. $c_1, c'_1$ is a $2$-coloring for $E_1$, therefore, $c_1 \neq
c'_1$. So $(c_1, c_2) \neq (c'_1,c'_2)$.
\epf

It is easy to see that this theorem is optimal with respect to the number
of colors used:  Figure 1 depicts the graph 
$K_4$ (the complete graph on $4$ vertices),
which can be easily decomposed into two trees but 
cannot be colored with fewer than 4 colors.

\begin{figure}
\psfig{figure=PS5.fig}
\caption{An example of a non 3-colorable graph that is union of two trees. }
\label{}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\thm
$\{\bar{\wedge}\}$ (NAND) is a complete basis but $\{\rightarrow\}$ is not.
\ethm

%	defined by $A \, \bar{\wedge} \, B = \neg(A \wedge B)$

\begin{proof}
\bparts
\ppart
$\{\bar{\wedge}\}$ is a complete basis.
We show how to implement $\neg$, $\land$, and $\lor$ with $\bar{\wedge}$:
	\begin{itemize}
	\item
	$\neg A = \neg (A  \wedge A) = A \, \bar{\wedge} \, A$
	\item
	$A \, \wedge \, B = \neg (\neg (A \, \wedge \, B) )
		= \neg (A \, \bar{\wedge} \, B)
		= (A \, \bar{\wedge} \, B) \, \bar{\wedge} \,
			(A \, \bar{\wedge} \, B)$
	\item
	$A \, \vee \, B = \neg (\neg A \, \wedge \, \neg B) )
		= \neg A \, \bar{\wedge} \, \neg B
		= (A \, \bar{\wedge} \, A) \, \bar{\wedge} \,
			(B \, \bar{\wedge} \, B)$
	\end{itemize}
Since $\{ \neg, \wedge, \vee \}$ is  a complete basis, so is 
$\{\bar{\wedge}\}$.
\ppart
$\{\rightarrow\}$ is not a complete basis since it can not simulate
$\neg$. Consider a circuit of $\rightarrow$-gates. 
At the bottom level we have only $A$'s as input.
If $A=T$, then each gate at the first level outputs $T$.
By induction on the levels, there is no way we can get $F$ as output from this 
$\rightarrow$ circuit. 
\eparts
\end{proof}


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

\thm The conjunction, disjunction, and composition of monotone
functions are monotone.
\ethm

\begin{proof}
Let $x \leq y$.  If $f$ and $g$ are monotone, then
$f(x) \leq f(y)$ and  $g(x) \leq g(y)$. 
\bparts
\ppart	Show $(f \wedge g)(x) = f(x) \wedge g(x)$ is monotone:\\
$f(x) \wedge g(x) = \min(f(x), g(x)) \leq \min(f(y), g(y)) = 
f(y) \wedge g(y)$.  Therefore, $(f \wedge g)(x) \leq
(f \wedge g)(y)$. So $(f \wedge g) $ is monotone.

\ppart  Show $(f \vee g)(x) = f(x) \vee g(x)$ is monotone:\\
 $f(x) \vee g(x) = \max(f(x), g(x)) \leq \max(f(y), g(y)) = 
f(y) \vee g(y)$.  Therefore, $(f \vee g)(x) \leq
(f \wedge g)(y)$.  So $(f \vee g) $ is monotone.

\ppart  Show $(f \circ g)(x) = f(g(x_1)g(x_2) \ldots g(x_n))$ is monotone:\\
$g$ is monotone implies that $g(x_i) \leq g(y_i)$ for all $1 \leq i \leq
n$. Let $x' = g(x_1)g(x_2) \ldots g(x_n)$ and $y' = g(y_1)g(y_2) \ldots 
g(y_n)$, then $x' \leq y'$. So $f(x') \leq f(y')$, since $f$ is monotone.
That is $(f \circ g)(x) \leq (f \circ g)(y)$. So $(f \circ g)$ is 
monotone.
\eparts
\end{proof}

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

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

\begin{proof}
Let $\Lambda = \{ A \rightarrow (B \wedge D), B \rightarrow D\} $.
\begin{enumerate}
\item 	$\Lambda  \vdash A \rightarrow (B \wedge D) $ \hfill $\psi\in\Ga$. 
\item 	$\Lambda \cup \{A\} \vdash A \rightarrow (B \wedge D) $
		\hfill 	from rule 10 and step 1.
\item 	$\Lambda \cup \{A\} \vdash A$
		\hfill 	$\psi\in\Ga$. 
\item 	$\Lambda \cup \{A\} \vdash B \wedge D$
		\hfill 	from rule 4 and step 2 and 3.
\item 	$\Lambda \cup \{A\} \vdash D \wedge B$
		\hfill 	from rule 11, $D \wedge B = B \wedge D$ and step 4.
\item 	$\Lambda \cup \{A\} \vdash D$
		\hfill 	from rule 6 and step 5.
\item 	$\Lambda \vdash A \rightarrow D$
		\hfill 	from rule 3 and step 6.
\end{enumerate}

\end{proof}


\end{problems}

\end{document}
