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

% 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 5\hfill \name}
\vskip 1em

% left column
\begin{minipage}[t]{0.75\textwidth}
Due \textbf{Feb 25} 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{4.32}{
Show that there is exactly one positive $k$ such that no graph contains exactly $k$ spanning trees.
}

\textbf{Solution:}


\question{4.34}{
(a) Find the number of spanning trees in the graph $G$ depicted below\\
(b) Find the number of spanning trees in the graph $G_k$ for $k \geq 5$ depicted below.
 [Note that (a) is the case where k = 4. $C_k$ stands for a cycle on $k$ vertices.]
\begin{center}
\begin{tikzpicture}
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
(0,0) node[label=left:$ $](a){} -- ++(0:1) node[label=above:$ $](b){} -- ++(120:1) node[label=above right:$ $](c){} 
--  (a) -- ++(150:1) node[label=below:$ $](x){}    (c) -- ++(150:1) node[label=below:$ $](y){}
(a) -- ++(270:1) node[label=below:$ $](k){}    (b) -- ++(270:1) node[label=below:$ $](l){}
(b) -- ++(30:1) node[label=below:$ $](m){}    (c) -- ++(30:1) node[label=below:$ $](n){}
(x)--(y) (k)--(l)  (m)--(n);
\draw (0.5,-1.5) node {$G$}
;
\end{tikzpicture}
\hskip 4em
\begin{tikzpicture}
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
(0,0) node[label=left:$ $](a){} -- ++(0:1) node[label=above:$ $](b){} -- ++(120:1) node[label=above right:$ $](c){} 
--  (a) -- ++(160:1) node[label=below:$ $](x){}    (c) -- ++(140:1) node[label=below:$ $](y){}
(a) -- ++(260:1) node[label=below:$ $](k){}    (b) -- ++(280:1) node[label=below:$ $](l){}
(b) -- ++(20:1) node[label=below:$ $](m){}    (c) -- ++(40:1) node[label=below:$ $](n){};
\draw[dashed]
(x) to[bend left=80,looseness=1.5] (y) (k)to[bend right=80,looseness=1.5] (l)  (m)to[bend right=80,looseness=1.5] (n);
\draw
(a) ++(0:0.5) ++(270:0.9) node{$C_k$}
(b) ++(120:0.5) ++(30:0.9) node{$C_k$}
(a) ++(60:0.5) ++(150:0.9) node{$C_k$}
;
\draw (2,-1.5) node {$G_k$}
;
\end{tikzpicture}
\end{center}
 }


\textbf{Solution:}


\question{4.40}{
Let $T$ and $T'$ be two spanning trees of a connected graph $G$ of order $n$. Show that there exists a sequence $T = T_0, T_1,\ldots, T_k = T'$ of spanning trees of $G$ such that $T_i$ and $T_{i+1}$ have $n-2$ edges in common for each $i$ with $1\leq i \leq k -1$.
}



\textbf{Solution:}


\question{}{
Count the number of spanning trees of the depicted graph using Matrix Tree Theorem.
\begin{center}
\begin{tikzpicture}
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
(0,0) node[label=left:$ $](a){} -- ++(45:1) node[label=above:$ $](b){} -- ++(-45:1) node[label=above right:$ $](c){} 
(a) -- ++(-45:1) node[label=below:$ $](d){} -- (c)   (a)--(c)
(c) -- ++(0:1) node{}
(a) -- ++(180:1) node{}
;
\end{tikzpicture}
\end{center}
}

\textbf{Solution:}

\question{}{
Count the number of spanning trees of $K_n$ using Matrix Tree Theorem.
}

\textbf{Solution:}

\question{}{
Let $G$ be a graph, which may also contain loops and multiple edges.
Let $e$ be an edge that is not a loop. Define $G-e$ as $G$ with the edge $e$ deleted,
and $G:e$ as the graphs arising from $G$ by deleting the edge $e$ and subsequent
gluing of the end-vertices of $e$ into a single vertex. The other edges are preserved, and so this operation can produce new loops or multiple edges.\\
Let $T(H)$ denote the number of spanning trees of graph $H$.\\
(a) Prove that $T(G) = T(G-e) + T(G:e)$.\\
(b) Derive the number of spanning trees of the 3-dimensional cube by a calculation based on (a)
}



\textbf{Solution:}






\end{document}














