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



\section*{External Link}
\url{https://w.wiki/8CGb}

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