
\documentclass[10pt]{article}
\usepackage{amsmath,amssymb,amsfonts,fancyhdr}
\usepackage{graphicx}
%
\setlength{\textheight}{9in}
\setlength{\topmargin}{-0.75in}
\setlength{\textwidth}{7in}
\setlength{\oddsidemargin}{-.2in}
\setlength{\parskip}{6pt}
\setlength{\parindent}{0pt}
%\usepackage{fullpage}
\renewcommand{\headrulewidth}{1pt}
\setlength{\headsep}{1cm}
% \usepackage{txfonts}
\usepackage{newcent}
\usepackage{fancyhdr}
\usepackage{multirow}   % for table formatting
\usepackage{hyperref}  % for weblinks in pdf
\usepackage{color}


\newcommand{\ds}{\displaystyle} 
\newcommand{\QQ}{{\mathbb{Q}}} % blackboard Q
\newcommand{\Qbar}{{\overline{\QQ}}} % blackboard Qbar
\newcommand{\ZZ}{{\mathbb{Z}}} % blackboard Z
\newcommand{\NN}{{\mathbb{N}}} % blackboard N
\newcommand{\CC}{{\mathbb{C}}} % blackboard C
\newcommand{\Zplus}{{\mathbb{Z^+}}} % blackboard Z^+
\newcommand{\FF}{{\mathbb{F}}} % blackboard F
\newcommand{\RR}{{\mathbb R}} % blackboard R
\newcommand{\Rtwo}{{\mathbb R^2}} % blackboard R^2
\newcommand{\Rthree}{{\mathbb R^3}} % blackboard R^3
\newcommand{\RRn}{{\mathbb R^n}} % blackboard R^n
\newcommand{\D}{{\cdot}} % dot
\def\mod#1{{\ifmmode\text{\rm\ (mod~$#1$)}
\else\discretionary{}{}{\hbox{ }}\rm(mod~$#1$)\fi}}

\def\tra{70}   %text rotation angle in table header
\newcommand{\tablehead}[1]{\rotatebox{\tra}{\scriptsize{#1}}}


%----------- colours ------------------------------------------------------
\definecolor{SFUred}{rgb}{0.60547,0.140625,0.17969}
\definecolor{SFUblue}{rgb}{.1602, .2734, .51172}
\definecolor{SFUgrey}{rgb}{.28515,.28125,.25}

\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%------------------------------------------------------------------------------
%amps stuff

\usepackage{enumitem}
\setlist[enumerate,1]{label=}
\setlist[enumerate,2]{label=\Alph*.}
\setlist[enumerate,3]{label=\arabic*.}
\setlist[enumerate,4]{label=(\alph*)}



% check boxes for after instructors questions
\newcommand{\insertcheckboxes}{
\begin{center}
\fbox{
\begin{tabular}{ccccc}
done & checked & corrected & study MT & study final \\
$\Box$ &  $\Box$ &  $\Box$ &  $\Box$ &  $\Box$
\end{tabular}
}
\end{center}
}


% standard basis vectors
\def\ihat{{\bf \hat{i}}}
\def\jhat{{\bf \hat{j}}}
\def\khat{{\bf \hat{k}}}

% vector arrow notation
\newcommand{\bvec}[1]{\vec{ \bf #1}}  % absolute value


\newcommand{\twovec}[2]{\left[\begin{array}{c}
#1\\ #2\\ \end{array}\right] }

\newcommand{\closethegap}{\vspace{-2mm} }

\newcommand{\threevec}[3]{\left[\begin{array}{c}
#1\\ #2\\ #3\\ \end{array}\right] }

\newenvironment{soln}[1]{ \textit{Solution #1:} }{\medskip}

\pagestyle{plain}

%------------------------------------------------
% different types of labels for lists
% 1) type of label
%\renewcommand{\theenumi}{\arabic{enumi}}   default
%\renewcommand{\theenumi}{\alph{enumi}}     alphabetic   (use capital A for capitals)
%\renewcommand{\theenumi}{\roman{enumi}}    roman numerals (use capital R for capitals)
%
% 2) formatting of label
%\renewcommand{\labelenumi}{(\theenumi)}   default
%\renewcommand{\labelenumi}{\theenumi.}    remove brackets
%------------------------------------------------


%------------ Course Information --------------------
\newcommand{\coursename}{Discrete Mathematics II}
\newcommand{\coursenum}{MACM 201 - D100 and D200}
\newcommand{\semester}{Fall 2020}
\newcommand{\instructor}{Jamie Mulholland and Michael Monagan}

%------------ Assignment Information -------------
\newcommand{\anum}{7}
\newcommand{\duedate}{Wednesday November 25, 2020}
\newcommand{\duetime}{11:59pm}

\pagestyle{fancy}
\fancyhf{} 

\lhead{\includegraphics[height=1cm]{logo.png}}
\rhead{\large\sc \coursenum ~~~~Assignment\ \#\anum}
\lfoot{ {\color{blue} \sc Copyright \instructor}}
\rfoot{{\small \thepage}}



%--------- Now for the document ----------------------------------

\begin{document}
\hfill{{\bf Due Date}:     \duedate, \duetime}
%\vspace{-0.75cm}
\subsection*{Instructions}
Answer all questions on paper or a tablet using your own handwriting.
Put your name, student ID number and page number at the top of each page.
If you use paper make a photo of each page and upload your solutions to crowdmark.
If you use a tablet, export your assignment to .pdf and upload the .pdf to crowdmark.

\begin{enumerate}
\item { \color{SFUred} \textbf{Textbook Reading} }  

		\begin{itemize}	
			\item Sections: 11.4, 11.5, 12.1
                \end{itemize}


%=====================================
% Definitions, Concepts & Keywords
%=====================================
%\item {\color{SFUred}\textbf{Definitions, Concepts \& Keywords}}
%\textbf{Definitions, Concepts \& Keywords}:
%
%   \begin{itemize}
%   \item[$\bullet$] Know what the following kinds of graphs are: 
%                    planar graph, dual graph, graph complement,
%                    Hamiltonian path, Hamiltonian cycle, and tree.
%   \item[$\bullet$] Kuratowski's theorem and Euler's theorem for planar graphs.
%   \item[$\bullet$] Understand multi graphs.
%   \end{itemize}

\item {\color{SFUred}\textbf{Exercises}}

   \begin{enumerate}

   %=====================================
   % Textbook Questions
   %=====================================	
   \item  \textbf{Textbook Questions} 

        \begin{itemize}
        \item[] 11.4 Exercises 2, 14ad, 26abc.
        \item[] 11.5 Exercises 1, 6.
        \item[] 12.1 Exercises 4, 6, 10
        \end{itemize}

   \item \textbf{Instructor Questions}

{Questions on 11.4}

    \begin{enumerate}
    \item
         Find a subgraph of the graph $G$ below that is subdivision
         of $K_{3,3}$.  Conclude that $G$ is not planar.

         \bigskip
         \quad \includegraphics[width=1.8cm]{cube.png}
         \medskip
    \item Let $G=(V,E)$ be a connected simple graph with $|V| \ge 11$. \\
          Show that $G$ or its complement $\bar G$ is not planar.
    \item Draw a planar embedding of the tetrahedron $T$.
          Draw $T^*$ the dual of $T$.

    \item The graph below is the Petersen graph.  It has 10 vertices and 15 edges.

         \medskip

         \quad \includegraphics[width=2.5cm]{Petersen.png}

         \medskip

         In class we derived the following edge bound for planar graphs.
\medskip

\quad \fbox{
\begin{minipage}{11cm}
\textbf{Theorem}: Let $G = (V,E)$ be a connected planar graph with $|V| \ge 3$. \\
If $G$ has no cycle of length 3 or less then $ |E| \le 2 |V| - 4. $
\end{minipage}
}

\medskip

          Notice in the Petersen graph there are cycles of length 5 but 
          none of 4 or less.  Derive a similar edge bound for this case and
          use it to prove that the Petersen graph is not planar.

    %\item Let $G=(V,E)$ be a connected planar simple graph with $|V| \ge 3$.
    %      If $G$ has no cycles of length 3 then $|E| \le 2 |V|-4.$
    % We proved two bounds on the number of edges that $G$ can have:
    %      \begin{itemize}
    %      \item[(1)] $|E| \le 3|V|-6$ and 
    %      \item[(2)] if $G$ has no cycles of length 3 then $|E| \le 2|V|-4$.
    %      \iten{itemize}
    %      A bound is said to be ``tight'' if there
    %      is an example which equals the bound.  Show that the two bounds
    %      are tight for $|V|=6$.  That is
    %      \begin{itemize} 
    %      \item[(1)] Find a connected simple planar graph 
    %                 with $|V|=6$ and $|E|=3|V|-6=12$ edges.
    %      \item[(2)] Find a connected simple planar graph 
    %                 with $|V|=6$ and $|E|=2|V|-4=8$ edges which does
    %                 not have a cycle with 3 edges.
    %      \end{itemize}
    \end{enumerate}

{Questions on 11.5}

    \begin{enumerate}[resume]
    \item Recall that $K_{m,n}$ denotes the complete bipartite graph with $m+n$ vertices.
          \begin{itemize}
          \item[(a)] Does $K_{2,3}$ have a Hamiltonian cycle?  
                     If yes draw one.  If not explain.
          \item[(b)] Does $K_{2,3}$ have a Hamiltonian path?  
                     If yes draw one.  If not explain.
          \item[(c)] Find the $K_{m,n}$ with the fewest vertexes which has
                     a Hamiltonian cycle.
          \item[(d)] Find the $K_{m,n}$ with the fewest vertexes which has
                     a Hamiltonian path.
          \end{itemize}
    \item Below is a non-planar drawing of the cube graph.
          \bigskip
          
         \quad \quad \includegraphics[width=2.5cm]{Cube.png}

         \medskip
          Draw a planar embedding of the cube graph. \\
          Draw all Hamiltonian cycles that include the edge $\{1,2\}$.
          I found four.
    \item What is the converse of Theorem 11.8? \\
          Give a counter example to the converse of Theorem 11.8.
    \end{enumerate}

{Questions on 12.1}

    
    \begin{enumerate}[resume]
    \item If a tree has four vertices of degree 2, four of degree 4, and two
          of degree 5, how many pendant vertices does it have?

    \item In class we proved the following theorem:
\begin{quote}
          If $T=(V,E)$ is a tree and $u,v\in V$ are distinct, there is a 
          unique path in $T$ from $u$ to $v$.
\end{quote}
          Prove that the converse of the theorem is also true, namely
\begin{quote}
          Let $G=(V,E)$ be a simple graph.
          If for every pair of vertices $u,v \in V$ there is a 
          unique path in $G$ from $u$ to $v$ then $G$ is a tree.
\end{quote}
    \end{enumerate}

  \end{enumerate}
\end{enumerate}

\end{document}

%
%=======================================================
%=======================================================
%=========                              ================
%=========  Selected Hints and Answers  ================
%=========                              ================
%=======================================================
%=======================================================
\end{enumerate}
\end{enumerate}

%\item {\color{SFUred}\textbf{ Selected Hints \& Answers}}
%
%Some final answers are given below. This is to provide you instant feedback on the validity of your solution - i.e. a quick check if your line of reasoning is correct. A complete solution requires full justification as to why these are the answers. 
%
\end{itemize}
\end{document}
