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

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

\begin{document}
\headers{Math378}{Homework 14}{Due Fri. May 2, 2025}

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

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

\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item The \emph{$k$-dimensional hypercube} $Q_k$ has vertex set $\{0,1\}^k$ (all bitstrings of length $k$) with $u$ and $v$ adjacent if and only if $u$ and $v$ differ in one position.  Prove that $Q_k$ is bipartite.

\item {} [10.3.10] Let $G$ be a multigraph with $n$ vertices and $m$ edges.  Show that $G$ has a bipartite subgraph that has $n$ vertices and at least $m/2$ edges.

\item {} Let $G$ be a $k$-regular bipartite graph.  Prove that $E(G)$ can be partitioned into perfect matchings.  (Hint: use Hall's Theorem to show that $G$ has a perfect matching and then use induction on $k$.)

\item {} [10.7.4] Let $G$ be a graph.  Prove that $\chi(G) \le 2$ if and only if $G$ is bipartite.

\item {} [10.7.5] Let $G$ be an $n$-vertex graph.  Prove that $\alpha(G)\cdot \chi(G) \ge n$.

\item {} Chromatic number and odd cycles.
	\begin{enumerate}
		\item Let $G$ be a graph such that $\chi(G)\ge 9$.  Prove that $G$ has three vertex-disjoint odd cycles.
		\item Find an example of a graph $G$ with $\chi(G)=8$ such that $G$ does not contain three vertex-disjoint odd cycles.
	\end{enumerate}


\end{enumerate}
\end{document}
