\documentclass{article}
\input{6045preamble}


\begin{document}
\homework{0}{Prof. Ron Rivest}{12 February 2002}{Your name goes here}

\begin{problem}
  Construct truth tables for each of the following formulae. Additionally,
  for  each
  pair of formulae, state which of the following holds:
  \begin{itemize}
  \item They are equivalent,
  \item They are not equivalent, but one implies the other (make sure
    to state which is which), or
  \item Neither of the above:
  \end{itemize}

  \begin{enumerate}
  \item $(p \vee q) \implies (p \wedge q)$
  \item $q \vee (\lnot q \implies p)$
  \item $(p \implies q) \wedge (q \implies p)$
  \item $(\lnot p \implies q) \wedge (\lnot q \implies p)$
  \end{enumerate}
\end{problem}


\begin{solution}
%
%
%
  Your solution goes here. Here is how you make a table in LaTeX:

$$
\begin{array}{c|c|c}
p & q & p \vee q \\ \hline
\true & \true & \true \\
\true & \false & \true \\
\false & \true & \true \\
\false & \false & \false
\end{array}
$$
%
%
%
\end{solution}


\begin{problem}
  Let $\Int$ be the set of Integers. Let $R$ be the relation 
  on $\Int$ such that $\{a,b\} \in R$ if, and only if, $ab > 0$.
  \begin{enumerate}
  \item Is $R$ Reflexive?
  \item Is $R$ Symmetric?
  \item Is $R$ Transitive?
  \item Define a proper subset of $R$ that has exactly one of the
        above three properties.  
  \end{enumerate}
\end{problem}


\begin{solution}
%
%
%
  Your solution goes here
%
%
%
\end{solution}



\begin{problem}
  A \emph{Hamiltonian cycle} in an undirected graph is a cycle that
  goes through every vertex in the graph exactly once. In this problem,
  we consider a special class of graphs which we will 
  call \emph{Happy} graphs. A Happy graph is one that has the following
  properties. 
  \begin{enumerate}
  \item The graph has $2n$ vertices for $n \geq 2$.
  \item For all $n > i \geq 1$. The graph has at least $2n - 2i + 2$
        vertices of degree greater than or equal to $n + i$.
  \end{enumerate}
  
  \textbf{Part A:}
  Prove that for $n = 2$, all Happy graphs with $2n$ vertices have
  a Hamiltonian cycle.

  \textbf{Part B:} Let $H$ be a Happy graph with $n \geq 3$. Prove 
  that if you remove two vertices of minimal degree from $H$ then 
  the resulting graph is also Happy.

  \textbf{Part C:}
  Prove that every Happy Graph has a Hamiltonian Cycle. (Hint:
  Use induction as well as the results from parts A and B).
\end{problem}


\begin{solution}
%
%
%
  Your solution goes here
%
%
%
\end{solution}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: