\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}}
\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}