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

% left column
\begin{minipage}[t]{0.75\textwidth}
Due \textbf{Apr 14} 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{}{
Find 0-factor, 1-factor, 2-factor, 3-factor and 4-factor in the following graph
\begin{center}
\begin{tikzpicture}
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
(0,0) node(a){} -- ++(45:1) node(b){} -- ++(135:1) node(c){}
-- ++ (-1,0) node(d){} -- ++(225:1) node(e){} -- ++(-45:1) node(f){} -- (a) -- (c) (d) -- (f) 
(b) -- ++(70:1.5) node(x){}
(b) -- ++(-70:1.5) node(y){}
(e) -- ++(70:-1.5) node(w){}
(e) -- ++(-70:-1.5) node(z){}
(x)--(y)--(w)--(z)--(x)
(a)--(y) (c)--(x)  (d)--(z) (f) --(w) 
;
\end{tikzpicture}
\end{center}
}

\textbf{Solution:}


\question{}{
Show that every 3-regular bridgeless graph contains a 2-factor.
}

\textbf{Solution:}

\question{}{
For each $k > 1$ construct a $k$-regular simple graph having no 1-factor.
}

\textbf{Solution:}

\question{}{
Prove that every graph without isolated vertices has a matching of size at least
$\frac{|V(G)|}{1+\Delta(G)}$.
}

\textbf{Solution:}


\question{}{
In an $X$,$Y$-bigraph $G$, the \textbf{deficiency} of a set $S$ is $def(S) = |S|-|N(S)|$; note that $def(\emptyset) = 0$. 
Prove that $\alpha'(G) = |X| - \max_{S \subseteq X} def(S)$.
(Hint: Form a bipartite graph $G'$ such that $G'$ has a matching that saturates $X$ if and only if $G$ has a matching of the desired size, and prove that $G'$ satisfies Hall's Condition.)
}

\textbf{Solution:}


\question{}{
Let $G$ be a bridgeless 3-regular graph. Let $e$ be any edge of $G$.
Show that there exists a perfect matching $M$ in $G$ such that $e \not\in G$.
}

\textbf{Solution:}




\end{document}














