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

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

\begin{document}
\headers{Math573}{Homework 3}{Due Thurs, Oct. 5, 2017}

%\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 $G$ be a nonbipartite triangle-free graph with $n$ vertices and minimum degree $k$.  Let $l$ be the minimum length of an odd cycle in $G$.
\begin{enumerate}
    \item Let $C$ be a cycle of length $l$ in $G$.  Prove that every vertex not in $V(C)$ contains at most two neighbors in $V(C)$.
    \item By counting the edges joining $V(C)$ and $V(G) - V(C)$ in two ways, prove that $n \ge kl/2$ (and thus $l\le 2n/k$).
    \item When $k$ is even, prove that the inequality of part (b) is best possible.  (Hint: form a graph having $k/2$ pairwise disjoint $l$-cycles.)
\end{enumerate}

\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 {} [IGT 1.4.29] Suppose that $G$ is a graph and $D$ is an orientation of $G$ that is strongly connected.  Prove that if $G$ has an odd cycle, then $D$ has a (directed) odd cycle.  (Hint: consider each pair $\{v_i, v_{i+1}\}$ in an odd cycle $v_1\cdots v_k$ of $G$.)

\item {} [IGT 1.4.34] Let $G$ and $H$ be tournaments on the same vertex set.  Prove that $d_G^+(v) = d_H^+(v)$ for each vertex $v$ if and only if $G$ can be turned into $H$ by a sequence of direction-reversals on cycles of length $3$.

\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.



\end{enumerate}
\end{document}s
