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

% left column
\begin{minipage}[t]{0.75\textwidth}
Due \textbf{Feb 11} 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{}{
Prove that Jarn\'{\i}k's algorithm is correct. That is, it's output is a minimum spanning tree.
}

\textbf{Solution:}

\question{4.14}{
A certain tree $T$ of order 35 is known to have 25 vertices of degree 1, two vertices of degree 2, three vertices of degree 4, one vertex of degree 5 and two vertices of degree 6. It also contains two vertices of the same (unknown) degree $x$. What is $x$?
}

\textbf{Solution:}

\question{4.18}{
Show that a tree on $n$ vertices where vertices have degree only 1 and 3 contains $(n-2)/2)$ vertices of degree 3. (No drawing)
}

\textbf{Solution:}


\question{}{
Apply Kruskal's and Jarn\'{\i}k-Prim's algorithm to find minimum spanning tree of
\begin{center}
\begin{tikzpicture}[scale=1.5]
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
(0,0) node(a){} -- ++(45:1) node(b){} -- ++(-45:1) node(c){} -- ++(45:1) node(x){}
(a) -- ++(-45:1) node(d){} -- (c) -- ++(-45:1) node(y){}  (b)--(d) 
(x)-- (y)
;
\draw
(x)-- node[right]{1} (y)
(a)-- node[above]{1} (b)
(b)-- node[above]{2} (c)
(c) -- node[below]{3} (d)
(d)-- node[below]{2}(a)
(d) -- node[right]{4}(b)
(c) --node[above]{4} (x)
(c) --node[below]{5} (y)
;
\end{tikzpicture}
\end{center}
Show how the tree is created after each edge, that means, every algorithm should have
a series of pictures how the minimum spanning tree was created.
}

\textbf{Solution:}

\question{}{
Consider the following algorithm. Let $G$ be a connected graph and $w: E(G) \rightarrow \mathbb{R}$.
Order all edges of $G$ edges such that $w(e_1) \geq w(e_2) \geq w(e_3) \geq \cdots$. 
Start with $H = G$. 
Consider edges one by one according to the ordering, check if $e_i$ is in a cycle in $H$, and if so remove
$e_i$ from $H$.
Is it true that the result of this algorithm is a minimum spanning tree?
(No drawing)
}

\textbf{Solution:}


\question{}{
Every tree is bipartite. Prove that every tree has a leaf in its larger partite set (in both if they have equal size).
(No drawing)
}


\textbf{Solution:}






\end{document}














