\documentclass[12pt, a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{colonequals}
\newcommand{\PP}{{\mathcal P}}
\newcommand{\QQ}{{\mathcal Q}}
\newcommand{\VV}{{\mathcal V}}
\newcommand{\ch}{\mathrm{ch}}

\newtheorem{conjecture}{Conjecture}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{observation}[theorem]{Observation}

\begin{document}

The goal of this worksheet is to guide you through the proof of Grötzsch' theorem
(every planar triangle-free graph is 3-colorable)
using the reducible configurations and the discharging method.

Actually, we will prove a stronger claim.
A face $f$ of a plane graph $G$ is \emph{bound} if there exists
a cycle $C$ in $G$ of length at most four such that $f$ is drawn inside $C$;
otherwise, we say that $f$ is \emph{free}.

\begin{theorem}\label{thm-main}
Let $G$ be a triangle-free graph drawn in the plane so that the outer face
of $G$ is bounded by a cycle $C$ of length at most six.  If $|C|=6$, furthermore
assume that $G$ has a free face (distinct from the outer one) of length at least five.
For every $3$-coloring $\psi$ of $C$, there exists a $3$-coloring $\varphi$ of $G$
that extends $\psi$.
\end{theorem}

\textbf{How does Theorem~\ref{thm-main} imply Grötzsch' theorem?}

\newpage

A (hypothetical) \emph{counterexample} is a pair $(G,\psi)$, where $G$
is a graph satisfying the assumptions of Theorem~\ref{thm-main} and $\psi$
is a 3-coloring of the cycle bounding its outer face such that $\psi$ does
not extend to a $3$-coloring of $G$.  A \emph{minimal counterexample}
is a counterexample with the smallest number of vertices.
Throughout the worksheet,
\begin{itemize}
\item let $(G,\psi)$ be a minimal counterexample,
\item let $C$ be the cycle of length at most six bounding the outer face of $G$, and
\item if $|C|=6$, then let $g$ be a free face of $G$ of length at least five.
\end{itemize}

For a cycle $K$ in a plane graph $H$, let $H_K$ denote the subgraph of $H$
consisting of $K$ and the vertices and edges drawn inside $K$.  We say that $K$
is \emph{separating} if $H_K\neq K$ and $H_K\neq H$, i.e., at least one vertex or edge of $H$
is drawn inside $K$ and at least one is drawn outside of $K$.

\textbf{Prove that
\begin{itemize}
\item $G$ contains no separating cycles of length at most five, and
\item if $K$ is a separating $6$-cycle in $G$, then all faces of $G_K$ except for the one bounded by $K$ have length four.
\end{itemize}}

\newpage

Suppose $v_1v_2v_3v_4$ is a 4-cycle in $G$, necessarily bounding a 4-face $f$ distinct from the outer one.
Suppose that $v_1\not\in V(C)$ or $v_3\not\in V(C)$.
Let $G_1$ be the graph obtained from $G$ by identifying $v_1$ with $v_3$ to a single vertex (collapsing the face $f$).
\textbf{Prove that $G_1$ is triangle-free (hint: show that $G$ would contain a separating 5-cycle otherwise).
Furthermore, if $|C|=6$, prove that $g$ is a free face in $G_1$.}

\newpage

\textbf{Prove that $G$ does not have any 4-face, except possibly for the outer face in case $|C|=4$ (hint: Use the fact
that the counterexample $G$ is minimal and $|V(G_1)|<|V(G)|$.  If $v_1,v_3\in V(C)$, consider identifying $v_2$ with $v_4$, instead).}

\newpage

\textbf{Prove that $G$ does not have any face $f$ of length at least six, except possibly for the outer face in case $|C|=6$
(hint: Try identifying two vertices incident with $f$.  In case that $f=g$ and $|C|=6$, don't forget to show that the
resulting graph has a free face of length at least five (the fact that $G$ does not have 4-faces should make this easy)).}

\newpage

Suppose $v_1v_2v_3v_4v_5$ is a cycle in $G$ bounding a 5-face $f$, where $v_1, \ldots, v_4$ have degree three and do not belong to $V(C)$.
For $i\in\{1,\ldots,4\}$, let $x_i$ be the neighbor of $v_i$ not incident with $f$.  If moreover $x_1,x_2,x_3,x_4\not\in V(C)$,
we say that $f$ forms a \emph{configuration ($\star$)}.  Let $G_1$ be the graph obtained from $G$ by deleting $v_1$, \ldots, $v_4$,
identifying $x_2$ and $x_3$ to a single vertex $x$, and adding the edge $x_1x_4$.

\textbf{Prove that $G_1$ is triangle-free (hint: Show that any triangle in $G_1$ would correspond to a forbidden separating cycle in $G$.
Don't forget to consider the possibility that the triangle would contain both $x$ and the edge $x_1x_4.$)}

\newpage

\textbf{Prove that (in the case that $|C|=6$), at least one of the two faces of $G_1$ incident with the edge $x_1x_4$
is a free face of length at least five.}

\newpage

\textbf{Prove that $G$ does not contain any configuration ($\star$).}

\newpage

\textbf{Prove that $G$ is 2-connected, all vertices of degree two belong to $V(C)$,
and no two vertices of degree two are adjacent.}

\newpage

We now choose the initial charge $\ch_0(v)$ of each vertex $v$ and $\ch_0(f)$ of each face $f$ so that
vertices of degree four have initial charge $0$ and the sum of the initial charges is $-24$.

\textbf{Give the formulas for the initial charges of vertices and faces.  What is the initial charge of
a vertex of degree three, and of a face of length five?}

\newpage

\textbf{Before you look at the next page, think about what discharging rules you could use to ensure that
all faces except for the outer one and all vertices not belonging to $V(C)$ have non-negative final charge
(keep in mind that all faces except for the outer one have length five, there is no configuration ($\star$), etc.)}

\newpage

Next, we redistribute the charge as follows, to obtain the final charge:
\begin{itemize}
\item Each face $f$ of length five except for the outer one sends one unit of charge to each incident vertex of degree three that does not belong to $V(C)$.
\item Each face $f$ of length five except for the outer one sends one unit of charge to each incident vertex of degree two (necessarily belonging to $V(C)$.
\item For each edge $uv$ such that $u\in V(C)$ and $v$ is a vertex of degree three not belonging to $V(C)$,
$u$ sends one unit of charge to the face incident with $v$ that is not incident with the edge $uv$.
\end{itemize}

\textbf{Show that all faces except for the outer one and all vertices not belonging to $V(C)$ have non-negative final charge.}

\newpage

\textbf{Show that the sum of the final charges of the outer face and the vertices in $V(C)$ is at least $-21$, and finish the argument.}

\end{document}