\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Fary theorem}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 64}
\maketitle
\section*{Problem}
Prove that every simple planar graph
can be drawn with straight line segments as edges.
\newpage
\section*{Solution}
We'll only prove it for maximal planar graphs with three or more
vertices: that is,
graphs for which drawing any extra edge breaks planarity.
\begin{claim*}
In a maximal planar graph, every edge is part of a cycle and
every face is a triangle.
\end{claim*}
\begin{proof}
For the first part, there are no leaves,
so every vertex has degree at least $2$,
hence part of a cycle.
For the second part, note if there was a face with four or more
edges, one can draw a chord.
\end{proof}
We prove by induction the following claim:
\begin{claim*}
Every maximal planar graph $G$ whose unbounded face is a triangle
can be drawn with only straight line segments,
in such a way that the faces and points inside them
remain the same as in the original graph.
\end{claim*}
\begin{proof}
By induction. If $G$ is a triangle, we are done.
Otherwise, using the bound $E \le 3n-6$,
there is a vertex $v$ of degree at most $5$
other than the vertices in the unbounded face.
Mold $G-v$ with straight line segments.
By art gallery problem, $v$ can be connected to the vertices
in the face containing $v$, as desired.
\end{proof}
Since any planar graph can be redrawn such that
a triangle is the unbounded face, this implies the result.
\end{document}