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

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

\begin{document}
\headers{Math573}{Homework 3}{Due Tue Oct 15, 2024}

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

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

\newcommand{\ex}{\mathrm{ex}}

\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_{i=1}^n 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 Determine with proof $\ex(n,P_n)$, the maximum number of edges in an $n$-vertex graph that does not contain a spanning path.

\item {}
\begin{enumerate}
    \item Prove that every connected graph has an orientation in which the number of vertices with odd outdegree is at most 1.  (Hint: consider an orientation with the fewest number of vertices with odd outdegree.)
    \item Use part (a) to conclude that every connected graph with an even number of edges has a $P_3$-decomposition.
\end{enumerate}

\item {} Let $G$ be a directed graph without loops.  Prove that $G$ has an independent set $S$ such that every vertex in $G$ is reachable from a vertex in $S$ by a directed path of length at most $2$.  Hint: use induction on $|V(G)|$ and recall that the induction hypothesis applies to all graphs with fewer vertices, not just graphs with $|V(G)|-1$ vertices.

\item {} \emph{Counting in tournaments.} Let $T$ be an $n$-vertex tournament.
\begin{enumerate}
	\item Prove that $T$ has $\binom{n}{3} - \sum_{v\in V(T)} \binom{d^+(v)}{2}$ (directed) $3$-cycles.
	\item For odd $n$, prove that there is an $n$-vertex Eulerian tournament.
	\item For odd $n$, determine the maximum possible number of $3$-cycles in an $n$-vertex tournament.
\end{enumerate}

\end{enumerate}
\end{document}
