
\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, D200 and D300}
\newcommand{\semester}{Spring 2021}
\newcommand{\instructor}{Mahsa Faizrahnemoon, Michael Monagan and Amarpreet Rattan}

%------------ Assignment Information -------------
\newcommand{\anum}{7}
\newcommand{\duedate}{Tuesday April 6th, 2021}
\newcommand{\duetime}{11:00pm}

\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.
{\bf Write your name}, student ID number {\bf on the cover page} and 
list the questions you answered.
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 14b, 19, 26abc.
        \item[] 11.5 Exercises 3e, 6.
        \item[] 12.1 Exercises 3, 10
        \end{itemize}

   \item \textbf{Instructor Questions}

{Questions on 11.4}

    \begin{enumerate}
    \item Let $P = (V,E)$ be the graph given by 
          vertices $V=\{1,2,3,4,5\}$ and edges \\ 
               $E=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\},
                    \{1,5\},\{2,5\},\{3,5\},\{4,5\}\}.$
          \begin{itemize}
          \item[(a)] Draw a planar embedding of $P$ with straight lines.
          \item[(b)] Draw a planar embedding of $P^*$ the dual of $P$.
          \end{itemize}

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

         \bigskip
         \quad $G = $ \ \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 Let $G=(V,E)$ be a connected planar simple graph with $|V| \ge 3$.
          In class we proved the bound $|E| \le 3|V|-6$.
          %\item[(2)] if $G$ has no cycles of length 3 then $|E| \le 2|V|-4$.
          A bound is said to be ``tight'' if there
          is an example which equals the bound.  
          Show that the bound $|E| \le 3|V|-6$ is tight, that is
          find a connected planar simple 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{enumerate}

{Questions on 11.5}

    \begin{enumerate}[resume]
    %\item \begin{itemize}
    %      \item[(a)] Give an example of a graph which has an Euler circuit but
    %      no Hamiltonian cycle.
    %      \item[(b)] Give an example of a graph which has a Hamiltonian cycle
    %      but no Euler circuit.
    %      \end{itemize}
    %Keep this for an exam

    \item Let $G=(V,E)$ a simple connected bipartite graph with
          $V$ partitioned as $V = V_1 \cup V_2$.
          Prove or disprove the following
          \begin{itemize}
          \item[(a)] $|V_1|=|V_2|$ and $|V_1| \ge 2$ are necessary conditions
                     for $G$ to have a Hamiltonian cycle.
          \item[(b)] $|V_1|=|V_2|$ and $|V_1| \ge 2$ are sufficient conditions
                     for $G$ to have a Hamiltonian cycle.
          \end{itemize}

    \item State the converse of Theorem 11.8. \\
          Show that the converse of Theorem 11.8 is false
          by finding a counter example.

    \item Twelve students are to be seated in a row of 12 seats in a classroom.
          If each student knows at most 5 others, explain why it is possible
          to seat them in such a way that each student does not know the 
          student(s) sitting beside them.

    \end{enumerate}

{Questions on 12.1}

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

    \item Let $T=(V,E)$ be a tree.  User Euler's theorem for planar graphs
          to show that $|V|=|E|+1$.

    \item Let $T$ be a tree with at least 2 vertices.
          Prove that removing any edge disconnects $T$.

          %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}

\end{enumerate}
\end{enumerate}

\end{itemize}
\end{document}
