\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts,amsmath,amssymb,amsthm}

\PassOptionsToPackage{obeyspaces}{url}
\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref}
\usepackage{tikz}

\usepackage{enumitem}
\setlist{itemsep=0.5em}

%% header definitions
\def\course{MATH 314}
\def\assign{HW \#12}
\def\due{Apr 26}
\def\doclink{\url{https://mathematicaster.org/teaching/graphs2022/hw/hw12.tex}}

%% environments
% theorem style
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{defn}[theorem]{Definition}

% definition style
\theoremstyle{definition}
\newtheorem{problem}{Problem}

% custom
\newenvironment{solution}{\paragraph{Solution.}}{\qed}

%% custom commands
\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}}       % arXiv link
\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}}        % definition by equality
\newcommand*{\abs}[1]{\lvert #1\rvert}     % absolute values, cardinality
\newcommand*{\eps}{\varepsilon}            % prettier epsilon
\newcommand*{\R}{\mathbb{R}}               % real numbers
\newcommand*{\C}{\mathbb{C}}               % complex numbers
\newcommand*{\Q}{\mathbb{Q}}               % rational numbers
\newcommand*{\Z}{\mathbb{Z}}               % integers
\newcommand*{\N}{\mathbb{N}}               % natural numbers
\newcommand*{\F}{\mathbb{F}}               % field
\newcommand*{\family}{\mathcal{F}}         % family
\newcommand*{\GL}{\mathbf{GL}}             % general linear group
\newcommand*{\what}[1]{\widehat{#1}}       % wider hat
\newcommand*{\wbar}[1]{\overline{#1}}      % wider bar
\newcommand*{\mcal}[1]{\mathcal{#1}}       % mathcal
\newcommand*{\mbf}[1]{\mathbf{#1}}         % mathbf
\newcommand*{\mbb}[1]{\mathbb{#1}}         % mathbb

% operators
\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}}       % probability
\DeclareMathOperator*{\E}{\mathbb{E}}          % expectation
\DeclareMathOperator*{\Var}{\mathbf{Var}}      % variance
\DeclareMathOperator*{\Span}{span}             % span
\DeclareMathOperator{\tr}{tr}                  % trace
\DeclareMathOperator{\rank}{rank}              % rank
\DeclareMathOperator{\supp}{supp}              % support
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator{\comp}{comp}
\DeclareMathOperator{\len}{len}



\begin{document}
\pagestyle{empty}

\noindent
\begin{minipage}{.33\textwidth}
	\flushleft {\bf \course}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\centering {\bf \assign}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\flushright {\bf \due}
\end{minipage}
\vskip3pt
\hrule\hrule\hrule
\vskip5pt

\noindent {\footnotesize This document is from \doclink}
\vskip10pt

\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof.
You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem.
}

\vskip20pt


\begin{problem}[2 + 2 + 2 pts]
    \phantom{hi}
    \begin{enumerate}
        \item Let $G$ be a bipartite graph with parts $A,B$ where $\abs A=\abs B=n\geq 1$.
            Prove that if $\abs{E(G)}>n(n-1)$, then $G$ has a perfect matching.

            (It may be easier to rely on K\H{o}nig here instead of on Hall, but it's up to you. You could even just induct on $n$.)

        \item Let $G$ be a bipartite graph with parts $A,B$ and fix an integer $n\geq 1$.
            Let $A=A_1\sqcup\dots\sqcup A_n$ and $B=B_1\sqcup\dots\sqcup B_n$ be any partitions (some of the $A_i$'s or $B_j$'s may be empty).
            Note that $\abs A$ and $\abs B$ have nothing to do with $n$; $n$ is just the number of pieces in each partition.

            Prove that if $\abs{E(G)}<n$, then there is a bijection $\pi\colon[n]\to[n]$ such that $G$ has no edges between $A_i$ and $B_{\pi(i)}$ for each $i\in[n]$.

            You are free to use part 1 as a black-box even if you haven't proved it.
        \item For each positive integer $t$, prove that if $G$ is a $t$-critical graph, then $\lambda(G)\geq t-1$.

            (Hint: Consult the notes from 03-01. Use part 2 to ``merge independent sets''.)

            You are free to use parts 1 and/or 2 as a black-box even if you haven't proved then.

            N.b.\ Vertex-connectivity is a very different story...
            In particular, the obvious analogue for vertex-connectivity is false (in general).
            The ``Moser spindle'' is a counter-example when $t=4$, and there are many, many others.
    \end{enumerate}
\end{problem}


\begin{problem}[2pts]
    Let $g\geq 2$ be an integer and let $G$ be a connected plane graph on $n$ vertices wherein every face is bounded by a cycle of $G$.
    Prove that if $G$ has no cycles of length $g$ or smaller, then
    \[
        \abs{E(G)}\leq {g+1\over g-1}(n-2).
    \]
\end{problem}



\begin{problem}[2pts]
    Prove a special case of the $4$-color theorem: If $G$ is a planar, triangle-free graph, then $\chi(G)\leq 4$.
\end{problem}


\end{document}
