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

% left column
\begin{minipage}[t]{0.75\textwidth}
Due \textbf{Mar 31} 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 examples of the following graphs:\\
(a) graph $G_a$ that is connected, every vertex has degree at least two and $G_a$ is not 2-connected.\\
(b) graph $G_b$ that is connected, every vertex is in a cycle and $G_b$ is not 2-connected.\\
(c) graph $G_c$ that is 2-connected, has at least three vertices and it contains three distinct vertices $x,y,z$ such that there is no cycle containing 
all three vertices $x$, $y$ and $z$.
}

\textbf{Solution:}


\question{8.2}{
There are positions open in seven different divisions of a major company: advertising (a), business (b), computing (c), design (d), experimentation (e), finance (f) and guest relations (g). Six people are applying for some of these positions, namely:
\begin{center}
Alvin(A): a,c,f; Bernie (B): a,b,c,d,e,g; Connie (C): c,f; \\ Donald (D): b,c,d,e,f,g; Edward (E): a,c,f; Frances (F): a,f. 
\end{center} 
(a) Represent this situation by a bipartite graph.\\
(b) Is it possible to hire all six applicants for six different positions?
}

\textbf{Solution:}

\question{8.3}{
A connected bipartite graph $G$ has partite sets $U$ and $W$, where $|U| = |W| = k \geq 2$. Prove that if every two vertices of $U$ have distinct degrees in $G$, then $G$ contains a perfect matching.
}

\textbf{Solution:}

\question{}{
Prove that $\alpha(G) \geq \frac{|V(G)|}{\Delta(G)+1}$ for every graph $G$.
}

\textbf{Solution:}

\question{}{
Prove that every maximal matching in a graph  $G$ has at least $\alpha'(G)/2$ edges.
(Recall that maximum matching has size $\alpha'(G)$. Maximal matching is a set of edges, such that no other edge can be included, but it does not have to be maximum one.
For example consider a path on vertices $v_1,v_2,v_3,v_4$. Edges $v_1v_2,v_3v_4$ form a maximum matching. Edge $v_2v_3$ forms a maximal matching since there is no larger matching containing $v_2v_3$.) 
}

\textbf{Solution:}

\question{}{
Let $G$ be a bipartite graph. Prove that $\alpha(G) = |V(G)|/2$ if and only if $G$ has a perfect matching.
}

\textbf{Solution:}




\end{document}














