\documentclass[11pt]{article}
\usepackage{amsmath}  % this adds some math 
\usepackage{fullpage}
\usepackage{tikz}            % if you delete this, you will have trouble with the included picture. You can delete the picture.
\usepackage{chessboard}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{shapes.multipart}
\usetikzlibrary{arrows}

% If you have a problem, please let me know sooner than later

\newcommand\name{Chuck Norris} %%%%%%%%%%%%%%  WRITE YOUR NAME HERE



\newcounter{excounter}
\setcounter{excounter}{1}
\newcommand\question[2]{\vskip 1em  \noindent\textbf{\arabic{excounter}\addtocounter{excounter}{1}:} \emph{#1} \noindent#2}


% You can also erase this if you do not have package hancyhdr
% Fancy footnote......... 
\usepackage{fancyhdr}  %% If it does not work with your latex installation, you may just delete this...
\pagestyle{fancy}
\usepackage{lastpage}
\rfoot{\name, page \thepage/\pageref{LastPage}}
\cfoot{}
\rhead{}
\lhead{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}



%%% Note that you do not have to use this template. You can use your own writeup or make any adjustment to this one you like.
%%% This is provided only for your convenience. 


\begin{document}


{\bf MATH314  \hspace{1cm} HW 9\hfill \name}
\vskip 1em

% left column
\begin{minipage}[t]{0.75\textwidth}
Due \textbf{Apr 7} before class, \textbf{answer without justification will receive 0 points}.
The typing the HW in \LaTeX{} is optional. 
\end{minipage}
% right box for score column
\begin{minipage}[t]{0.25\textwidth}
\hfill \begin{tabular}{|r|}
\hline
\hskip 3em Score \hskip 3em \\
\hline \\ \\
\hskip 3em /60 \\
\hline
\end{tabular}
\end{minipage}





\question{}{
Decide if the following graph (called Gr\"otzsch's graph) is Hamiltonian.
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
\foreach \x in {0,...,4}{ (0,0)--(90+72*\x:1) node(x\x){}  (90+72*\x:2) node(y\x){}}
(0,0) node{}
(y0)--(y1)--(y2)--(y3)--(y4)--(y0)
(y0)--(x1)--(y2)--(x3)--(y4)--(x0)--(y1)--(x2)--(y3)--(x4)--(y0)
;
\end{tikzpicture}
\end{center}
}

\question{}{
A mouse eats its way through $3\times 3\times 3$ cube of cheese by tunneling through all of the 27 $1\times1\times1$ subcubes. The mouse starts at one corner of the cube and it always moves on to an uneaten subcube. Can it finish by eating the center of the cube last? (Ignore all gravity related problems - suppose the mouse is on the International Space Station.)
}

\textbf{Solution:}


\question{}{
Let $G$ be a Hamiltonian bipartite graph, and choose $x,y \in V(G)$. Prove that $G -x -y$ has a perfect matching if and only if $x$ and $y$ are on the opposite side of the bipartition of $G$. Apply this to prove that deleting two unit squares from an 8 by 8 chessboard leaves a board that can be partitioned into 1 by 2 rectangles if and only if the two missing squares have opposite color.
}

\textbf{Solution:}

\question{}{
On a chessboard, a \textbf{knight} can move from one square to another that differs by 1 in one coordinate and by 2 in the other coordinate, as shown in an example below. Prove that no $4 \times n$ chessboard has a \textbf{knight's tour}: a traversal by knight's moves that visits each square once and returns to the start. 
\begin{center}
\begin{tikzpicture}[scale=1]
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
(0,0) grid (6,4)
\foreach \x in {0,...,5}{ \foreach \y in {0,...,3}{ (\x+0.5,\y+0.5) node(a\x\y){}  }}
(a00)--(a12) (a00)--(a21) (a31)--(a43) (a32)--(a51)
;
\end{tikzpicture}
\end{center}
Notice that the question can be translated to a graph question and finding a Hamiltonian cycle.
}

\textbf{Solution:}


\question{}{
Prove that cartesian product of two Hamiltonian graphs in Hamiltonian.
}


\textbf{Solution:}


\question{}{
Let $G$ be a connected $r$-regular graph of even order $n$ such that $\overline{G}$  is also connected. Show that\\
(a) either $G$ or $\overline{G}$  is Eulerian.\\
(b) either $G$ or $\overline{G}$ is Hamiltonian.
}

\textbf{Solution:}




\end{document}














