\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{Russia 2010/10.8}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 73}
\maketitle

\section*{Problem}
Let $G$ be a finite connected graph.
Suppose that, if we choose any odd cycle in $G$ and delete all its edges,
the resulting graph is not connected.
Prove that we color each vertex of $G$ with one of four colors such that
no two adjacent vertices are the same color.

\section*{Video}
\href{https://www.youtube.com/watch?v=uDVCCdQLt6s&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/uDVCCdQLt6s}}

\section*{External Link}
\url{https://aops.com/community/p2013543}

\newpage

\section*{Solution}
Let $T$ be a spanning tree, and let $H$ be the subgraph
(not induced) of remaining edges.
\begin{itemize}
  \ii Trees are bipartite, so $T$ has a two-coloring.
  \ii By condition, $H$ has no odd cycles
  (since deletion of an odd cycle should disconnect $G$).
  Hence $H$ is bipartite, and has a two-coloring.
\end{itemize}
Then we can four-color $G$ using the ordered pair of two-colorings.

\end{document}
