\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{9: Matchings}{Due Friday, Week 6}


This problem set is centered around the concept of \textbf{matchings}!
\begin{defn}
A \textbf{matching} in a graph $G$ is a subgraph of $G$, consisting simply of edges and their endpoints, so that none of the edges of this subgraph have any endpoints in common.  A \textbf{maximum matching} in a graph $G$ is a matching with the largest number of edges possible.  A \textbf{perfect matching} is a matching that contains every vertex of $G$. 
\end{defn}
\begin{center}
\includegraphics[height=.7in]{match_ex.pdf}\\
\footnotesize Left: a graph $G$ with a perfect matching $M$.  Right: a graph $H$ with all possible nonempty matchings $M_1, M_2, M_3$, all of which are maximal, but none of which are perfect. \normalsize
\end{center}


Do \textbf{three} of the six problems listed here!  Have fun, prove all of your claims, and let me know if you have any questions!  Also, feel free to use the results of any problem here in your proofs of other problems, even if you don't turn in the solution to that problem!

Also, this set is tricky!  Spend time on this set.  
\begin{enumerate}
\item Given a matching $M$, a $M$-\textbf{augmenting path} is a path $P$ in $G$ that alternates between edges in $M$ and edges not in $M$, so that the two endpoints of $P$ are distinct and not in $M$.
\begin{center}
\includegraphics[height=.7in]{aug_path_ex.pdf}\\
\end{center}
Take any connected graph $G$ and any matching $M$ of $G$.  Show that $M$ is a maximum matching if and only if $G$ has no augmenting path. 
\item\label{hall1} Suppose that $G$ is a bipartite graph; write $V(G) = V_1 \cup V_2$, where $V_1, V_2$ are the two parts of $V(G)$.  

Suppose that $G$ has a perfect matching. Prove that $G$ has the following property: if we take any subset $S$ of $V_1$ or $V_2$, and let $N(S)$ denote the total number of vertices connected to elements of $S$, then $|S| \leq |N(S)|$.
\item Prove the converse of problem \ref{hall1}: Suppose that $G$ is a bipartite graph, such that for any subset $S$ of either $V_1$ or $V_2$, we have $|S| \leq N(S)$.  Then $G$ has a perfect matching.
\item A \textbf{vertex cover} of a graph $G$ is a subset of the vertices of $G$ that contains at least one endpoint of every edge.   Prove that for any bipartite graph $G$, the number of vertices in the smallest vertex cover is the same as the number of vertices in the largest matching.
\item Prove or disprove: every tree contains at most one perfect matching.
\item Consider the following two- player game, played on any graph $G$.  
\begin{itemize}
\item Player 1 starts by choosing a vertex $v_1$ in $G$.
\item Player 2 responds by taking any vertex $v_2$ that is adjacent to $v_1$ (i.e. is connected to $v_1$ by an edge.
\item Player 1 takes any vertex $v_3$ adjacent to $v_2$ that was not chosen yet.
\item Player 2 takes any vertex $v_4$ adjacent to $v_3$ that was not chosen yet.
\item \ldots
\item Play stops when one player is no longer able to move, in which case that player loses.
\end{itemize}
Show that player 2 has a winning strategy if and only if a perfect matching exists, and that otherwise player 1 has a winning strategy.
\end{enumerate}



\end{document}