Fary's Theorem

Lemma (Pentagonal Center)

Given any polygon $P$ in the plane with at most $5$ sides, there is a point $v$ inside of $P$ with straight line paths to each of $P$‘s vertices.

Proof: A triangle is trivial. We have $5$ cases:

Case 1: If we have no non-convex angles, then

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzcd}\n\t& \\bullet \\\\\n\t\\bullet & v & \\bullet \\\\\n\t\\bullet && \\bullet\n\t\\arrow[no head, from=1-2, to=2-3]\n\t\\arrow[no head, from=2-1, to=1-2]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=2-1, to=2-2]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=2-2, to=1-2]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=2-2, to=2-3]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=2-2, to=3-1]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=2-2, to=3-3]\n\t\\arrow[no head, from=2-3, to=3-3]\n\t\\arrow[no head, from=3-1, to=2-1]\n\t\\arrow[no head, from=3-3, to=3-1]\n\\end{tikzcd}\n\\end{document}"$

source code

any point on the interior works.

Case 2: If we have $1$ non-convex angle, then

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzcd}\n\t\\bullet && \\bullet \\\\\n\t& \\bullet \\\\\n\t& v \\\\\n\t\\bullet && \\bullet\n\t\\arrow[no head, from=1-1, to=2-2]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=1-1, to=3-2]\n\t\\arrow[no head, from=1-3, to=4-3]\n\t\\arrow[no head, from=2-2, to=1-3]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=3-2, to=1-3]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=3-2, to=2-2]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=3-2, to=4-1]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=3-2, to=4-3]\n\t\\arrow[no head, from=4-1, to=1-1]\n\t\\arrow[no head, from=4-3, to=4-1]\n\\end{tikzcd}\n\\end{document}"$

source code

then we can place $v$ inside the non-convex angle.

Case 3: If we have two adjacent non-convex angles,

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzcd}\n\t&& \\bullet \\\\\n\t&& v \\\\\n\t\\\\\n\t& \\bullet && \\bullet \\\\\n\t\\bullet &&&& \\bullet\n\t\\arrow[no head, from=1-3, to=5-5]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=2-3, to=1-3]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=2-3, to=4-2]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=2-3, to=4-4]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=2-3, to=5-5]\n\t\\arrow[no head, from=4-2, to=5-1]\n\t\\arrow[no head, from=4-4, to=4-2]\n\t\\arrow[no head, from=5-1, to=1-3]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=5-1, to=2-3]\n\t\\arrow[no head, from=5-5, to=4-4]\n\\end{tikzcd}\n\\end{document}"$

source code

then we can place near the opposite vertex.

Case 4: If we have two non-adjacent non-convex angles,

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzcd}\n\t&&&& \\bullet \\\\\n\t&&&&& \\bullet \\\\\n\t&&& \\bullet & v \\\\\n\t\\bullet &&&&&&&& \\bullet\n\t\\arrow[no head, from=1-5, to=2-6]\n\t\\arrow[no head, from=2-6, to=4-9]\n\t\\arrow[no head, from=3-4, to=1-5]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=3-4, to=3-5]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=3-5, to=1-5]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=3-5, to=2-6]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=3-5, to=4-1]\n\t\\arrow[color={rgb,255:red,214;green,92;blue,214}, no head, from=3-5, to=4-9]\n\t\\arrow[no head, from=4-1, to=3-4]\n\t\\arrow[no head, from=4-9, to=4-1]\n\\end{tikzcd}\n\\end{document}"$

source code

and we can place $v$ near the far wall so it can see all the vertices.

Case 5: If we more than two non-convex angles, then this cannot happen. In particular, the sum of angles for an $n-$gon is $180(n-2)$.

Corollary (Hexagonal Center)

No, this is not true for hexagons. Consider the following counter example:

$"\\usepackage{tikz-cd}\n\\begin{document}\n$

source code

which cannot have central vertex that keeps the graph planar.

Lemma (Triangulation Leads to Interior Vertex)

Let $G$ be a connected, planar graph. Let $|V|>3$. If $G$ is constructed by triangulation, then any such $G$ will have an interior vertex $v$ of ${\mathrm{deg}}_G(v)\le 5$.

Proof: By the Handshake Lemma, and theorem,

$$\sum _{v\in V}\mathrm{deg}(v)=2|E|=6|V|-12$$

Rearranging, we get

$$\sum _{v\in V}(6-\mathrm{deg}(v))=12$$

Since the graph is triangulated, the infinite face is a triangle, and thus bounded by $3$ boundary vertices. Then the degree of each is $2$, such that they can only contribute at most $4$, unless they do not connect anything else. Thus, some other vertex must have $6-\mathrm{deg}(v)>0$.

Fary’s Theorem

Any finite simple planar graph $G$ has a plane embedding where all of the edges are straight line segments.

Proof:

We proceed with induction on $|V|$. For $|V|\le 3$, this is trivial. Assume $G$ is connected (otherwise we can do this on each connected component separately).

Assume we can draw any graph with $n$ vertices as planar. WTS this is true for $|V|+1$. Suppose we triangulated the graph $G$ to get $G^{\prime }$. By Lemma (Triangulation Leads to Interior Vertex), we have some interior vertex $v$ where ${\mathrm{deg}}_{G^{\prime }}(v)\le 5$.

Consider graph $G^{\prime \prime }=G^{\prime }-\{v\}$. Then by the induction hypothesis, $G^{\prime \prime }$ is planar with straight lines. Since ${\mathrm{deg}}_{G^{\prime }}(v)\le 5$, then the face created in $G^{\prime \prime }$ is no more than a pentagon. By applying Lemma (Pentagonal Center), we can reinsert $v$ that makes the graph still planar, but with straight lines.