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

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

\begin{document}
\headers{Math573}{Homework 1}{Due Thu Aug 31, 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 {} Prove that the complement of a disconnected graph is connected.

\item {} Find a $P_6$-decomposition of the Petersen graph or show that no such decomposition exists.

\item {} In a graph, a $uv$-path is a path with endpoints $u$ and $v$.  Prove that if $G$ has a $uv$-path of length at least $k^2$ and some cycle in $G$ contains $u$ and $v$, then $G$ has a cycle of length at least $k+1$.

\item {} Let $G$ be a graph with girth $4$ in which every vertex has degree $k$.  Prove that $G$ has at least $2k$ vertices.  Determine all such graphs with exactly $2k$ vertices.

\item {} Prove that a self-complementary graph with $n$ vertices exists if and only if $n = 4k$ or $n=4k+1$ for some integer $k$.  Hint: When $n$ is divisible by $4$, generalize the structure of $P_4$ by splitting the vertices into four groups.  For $n$ of the form $n=4k+1$, add one vertex to the graph constructed for $n=4k$.

\item {} Let $G$ be a simple graph in which every vertex has degree $3$.  Prove that $G$ decomposes into claws if and only if $G$ is bipartite.

\end{enumerate}
\end{document}
