\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math573}{Homework 4}{Due Thurs, Oct. 26, 2017}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  All written work must be your own, using only permitted sources.  See the ``General Guidelines and Advice'' on the homework page for more details.

\begin{enumerate}

\item {} Let $d_1, \ldots, d_n$ be positive integers with $n\ge 2$.  Prove that there exists a tree with vertex degrees $d_1, \ldots, d_n$ if and only if $\sum d_i = 2n-2$.

\item {} For $n \ge 4$, let $G$ be an $n$-vertex graph with at least $2n-3$ edges.  Prove that $G$ has two cycles of equal length.

\item {} Tree Subgraphs
\begin{enumerate}
	\item Let $G$ be a connected graph on at least $k+1$ vertices such that $d(u) + d(v) \ge 2k-1$ whenever $u$ and $v$ have distance $2$ in $G$.  Prove that if $T$ is a tree with $k$ edges, then $T$ is a subgraph of $G$.  Hint: for each $j$ with $0\le j\le k$ and each tree $T_j$ with $j$ edges, obtain a copy of $T_j$ in $G$ in which each vertex in $T_j$ has a prescribed number of neighbors outside $T_j$.
	\item For $k\ge 3$, give an example of a connected graph $G$ on at least $k+1$ vertices such that $d(u)+d(v)\ge 2k-2$ and some tree with $k$ edges fails to be a subgraph of $G$.
\end{enumerate}
Comment: Since $\delta(G)\ge k$ implies that each component of $G$ satisfies the hypotheses in (a), this strengthens Proposition 2.1.8.

\item {} Use Cayley's Formula to prove that the graph obtained from $K_n$ by deleting an edge has $(n-2)n^{n-3}$ spanning trees.

\item {} Let $G$ be an $(X,Y)$-bigraph.  A \emph{near-matching} in $G$ is a set of edges $M$ such that each vertex in $X$ is the endpoint of at most one edge in $M$ and each vertex in $Y$ is the endpoint of at most two edges in $M$.  Find and prove an analogue of Hall's theorem that characterizes when $G$ has a near-matching saturating $X$.  (You may use Hall's theorem in the proof of your new characterization.)

\item {} Two people play a game on a graph $G$, alternately choosing distinct vertices.  Player 1 starts by choosing any vertex.  Each subsequent choice must be adjacent to the preceding choice (of the other player).  Thus together they follow a path.  The last player able to move wins.

Prove that the second player has a winning strategy if $G$ has a perfect matching, and otherwise the first player has a winning strategy.  (Hint: for the second part, the first player should start with a vertex omitted by some maximum matching.)

\end{enumerate}
\end{document}
