\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 2004 C3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 7}
\maketitle
\section*{Problem}
The following operation is allowed on a finite graph:
Choose an arbitrary cycle of length $4$ (if there is any),
choose an arbitrary edge in that cycle, and delete it from the graph.
For a fixed integer $n \ge 4$,
find the least number of edges of a graph that can be obtained
by repeated applications of this operation
from the complete graph on $n$ vertices.
\section*{Video}
\href{https://www.youtube.com/watch?v=0f4qSCsWQjI&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/0f4qSCsWQjI}}
\newpage
\section*{Solution}
The answer is $n$.
As the case $n=4$ is easily done by hand,
we will assume $n \ge 5$.
To show that at least $n$ edges always remain, note that
\begin{itemize}
\ii The operation preserves connectedness of the graph;
\ii The operation preserves the fact
that the graph is \emph{not} bipartite.
\end{itemize}
This implies the graph will always have $n$ edges leftover
(since a connected graph always has at least $n-1$ edges,
but with equality only when it is a tree,
and trees are necessarily bipartite).
Conversely, for any $n \ge 5$ one can reach the graph
consisting of a $K_5$ plus a path of length $n-5$ hanging
off one vertex.
Then one can prune the $K_5$ down to $C_5$ to achieve the
desired construction.
\begin{center}
\begin{asy}
draw(dir(0)--dir(72)--dir(144)--dir(216)--dir(288)--cycle, red);
draw(dir(0)--dir(144)--dir(288)--dir(72)--dir(216)--cycle, lightblue);
draw(dir(0)--2*dir(0), red);
draw(2*dir(0)--3*dir(0), red);
draw(3*dir(0)--4*dir(0), red);
dotfactor *= 1.5;
pen vtxpen = grey;
dot(dir(0), vtxpen);
dot(dir(72), vtxpen);
dot(dir(144), vtxpen);
dot(dir(216), vtxpen);
dot(dir(288), vtxpen);
dot(2*dir(0), vtxpen);
dot(3*dir(0), vtxpen);
dot(4*dir(0), vtxpen);
\end{asy}
\end{center}
\end{document}