\documentclass{article}%
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Thursday, August 21, 2008 14:03:59}
%TCIDATA{LastRevised=Wednesday, October 01, 2014 12:46:33}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{Language=American English}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}
\title{Math 443/543 Graph Theory Notes 5: Planar graphs and coloring}
\author{David Glickenstein}
\maketitle
\section{Planar graphs}
The Three Houses and Three Utilities Problem: Given three houses and three
utilities, can we connect each house to all three utilities so that the
utility lines do not cross.
We can represent this problem with a graph, connecting each house to each
utility. We notice that this graph is bipartite:
\begin{definition}
A \emph{bipartite graph} is one in which the vertices can be partitioned into
two sets $X$ and $Y$ such that every edge joins one vertex in $X$ with one
vertex in $Y.$ The partition $\left( X,Y\right) $ is called a
\emph{bipartition}. A \emph{complete bipartite graph} is one such that each
vertex of $X$ is joined with every vertex of $Y.$ The complete bipartite graph
such that the order of $X$ is $m$ and the order of $Y$ is $n$ is denoted
$K_{m,n}$ or $K\left( m,n\right) .$
\end{definition}
It is easy to see that the relevant graph in the problem above is $K_{3,3}.$
Now, we wish to embed this graph in the plane such that no two edges cross
except at a vertex.
\begin{definition}
A \emph{planar graph} is a graph that can be drawn in the plane such that no
two edges cross except at a vertex. A planar graph drawn in the plane in a way
such that no two edges cross except at a vertex is called a \emph{plane graph}.
\end{definition}
Note that it says \textquotedblleft can be drawn\textquotedblright\ not
\textquotedblleft is drawn.\textquotedblright\ The problem is that even if a
graph is drawn with crossings, it could potentially be drawn in another way so
that there are no crossings.
Thus the Three Houses and Three Utilities Problem is whether or not $K_{3,3}$
is a planar graph.
A planar graph divides the plane into regions. That is, if we remove the
vertices and edges from the plane, there are a number of disconnected pieces,
each of which we call a \emph{region}. The \emph{boundary} of a given region
is all of the edges and vertices incident on the region. Notice that there is
always one \emph{exterior region} which contains all of the unbounded parts of
the plane.
Look at examples. Notice that $p-q+r=2.$ A theorem of Euler says that this is
always true. For the following theorem, we will need the definition of a tree.
\begin{definition}
A connected graph with no cycles is called a \emph{tree}.
\end{definition}
Note the following fact about trees.
\begin{proposition}
A tree with $p$ vertices and $q$ edges satisfies $p=q+1.$
\end{proposition}
\begin{proof}
This can be proven by induction on the number of edges, since each time a new
edge is attached, it must come with a new vertex. This is because if we attach
two vertices with an edge, since the tree in the previous step is connected,
we had a path between the two vertices and are hence introducing a cycle.
\end{proof}
\begin{theorem}
[Euler's Theorem]Let $G$ be a connected plane graph with $p$ vertices, $q$
edges, and $r$ regions. Then
\[
p-q+r=2.
\]
\end{theorem}
We remark that the number 2 has to do with the plane, and will become
important when we look at topology.
\begin{proof}
We induct on $q.$ If $q=0,$ then we must have $p=1$ and $r=1.$ Thus
$p-q+r=1-0+1=2.$ Now suppose it is true for all graphs with $k$ or fewer
edges. Consider a connected graph $G$ with $k+1$ edges. If $G$ is a tree, then
we know that $p=q+1=k+2.$ Furthermore, since there are no cycles in a tree,
$r=1.$ Thus%
\[
p-q+r=\left( k+2\right) -\left( k+1\right) +1=2.
\]
If $G$ is not a tree, then it contains a cycle. Let $e\in G$ be an edge on a
cycle. If we look at $G^{\prime}=G-e,$ it has $k$ edges, and $p^{\prime}=p,$
$q^{\prime}=k=q-1,$ and by the inductive hypothesis,
\[
p^{\prime}-q^{\prime}+r^{\prime}=2.
\]
We see that $r^{\prime}=r-1$ since removing the edge $e$ joins the regions on
either side of the $e.$ Thus
\[
p-q+r=p^{\prime}-\left( q^{\prime}+1\right) +\left( r^{\prime}+1\right)
=2.
\]
\end{proof}
Notice the following corollary:
\begin{corollary}
Any representation of a planar graph as a plane graph has the same number of regions.
\end{corollary}
We can now solve the Problem of Three Houses and Three Utilities.
\begin{theorem}
The graph $K_{3,3}$ is not planar.
\end{theorem}
\begin{proof}
Suppose we can represent $K_{3,3}$ as a plane graph. We know that $p=6$ and
$q=9,$ so we need to understand something about $r.$ Since $K_{3,3}$ is
bipartite, we see that all regions have boundaries with at least 4 edges.
Suppose the graph divides the plane into regions $R_{1},R_{2},\ldots,R_{r}.$
Let $B\left( R\right) $ be the number of edges in the boundary of region
$R.$ Consider the number
\[
N=\sum_{i=1}^{r}B\left( R_{i}\right) .
\]
Since all regions have boundaries with at least 4 edges, we have
\[
N\geq4r.
\]
However, since each edge is counted twice, we have that
\[
N=2q=18.
\]
Thus
\[
4r\leq18
\]
or
\[
r\leq4.5.
\]
However, that would mean that
\[
p-q+r=6-9+r\leq1.5,
\]
which is impossible if the graph is a plane graph.
\end{proof}
One might ask about other non-planar graphs. Another important one is $K_{5}.$
Here is a theorem that allows us to show this.
\begin{theorem}
Let $G$ be a connected, planar graph with $p$ vertices and $q$ edges, with
$p\geq3.$ Then
\[
q\leq3p-6.
\]
\end{theorem}
\begin{proof}
The proof is quite similar to that of the previous theorem. For $p=3,$ we
certainly have $q\leq3.$ For $p\geq4,$ we consider a representation of $G$ as
a plane graph, which gives us $r$ regions. Denote the regions as $R_{1}%
,R_{2},\ldots,R_{r}.$ We compute again%
\[
N=\sum_{i=1}^{r}B\left( R_{i}\right) .
\]
This time, we note that $B\left( R\right) \geq3$ for each region, and a
similar argument give us that
\[
3r\leq N\leq2q.
\]
Using Euler Theorem, we have that
\begin{align*}
2 & =p-q+r\\
& \leq p-q+\frac{2}{3}q=p-\frac{1}{3}q
\end{align*}
or%
\[
q\leq3p-6.
\]
\end{proof}
\begin{corollary}
The complete graph $K_{5}$ is not planar.
\end{corollary}
\begin{proof}
We see that $K_{5}$ has $p=5$ and $q=\binom{5}{2}=10,$ and so
\[
q=10>15-6=3p-6.
\]
\end{proof}
\section{Kuratowski's theorem}
We saw that $K_{5}$ and $K_{3,3}$ are not planar. It easily follows that any
graph containing one of these as a subgraph (technically, any graph with a
subgraph isomorphic to one of these two graphs) is not planar either. In fact,
we can do slightly better by seeing that any graph with a subgraph isomorphic
to a subdivision of $K_{5}$ or $K_{3,3}$ is not planar.
\begin{definition}
A \emph{subdivision} of a graph $G$ is a new graph obtained by adding vertices
inside the edges. (The new vertices are all of degree 2.)
\end{definition}
It is then clear that :
\begin{proposition}
If a subdivision of $G$ is planar, then $G$ is planar.
\end{proposition}
\begin{proof}
Given a representation of the subdivision of $G$ as a plane graph, simply
remove the vertices which form the subdivision and we arrive at a plane graph
representation of $G.$
\end{proof}
Stated another way, if $G$ is not planar, then any subdivision is not planar.
Thus any subdivision of $K_{5}$ and $K_{3,3}$ is nonplanar.
\begin{proposition}
If $G$ is planar, then every subgraph is planar.
\end{proposition}
\begin{proof}
Represent $G$ as a plane graph, then the subgraphs are also plane graphs.
\end{proof}
Thus if a subgraph of $G$ is a subdivision of $K_{5}$ or $K_{3,3},$ then it is
not planar, and thus $G$ is not planar.
Kuratowski's theorem is the converse:
\begin{theorem}
[Kuratowski]If a graph is not planar, then it contains a subgraph isomorphic
to a subdivision of $K_{5}$ or $K_{3,3}.$
\end{theorem}
Proof is in BM1, BM2, or D. We may do it later in the semester.
\section{Topology comments}
Plane graphs are also graphs on spheres. Using stereographic projection, one
can convert any plane graph to a graph on the sphere with no vertex at the
north pole. Stereographic projection is a map from the sphere except the north
pole to the plane which is a homeomorphism (i.e., a bijection which is
continuous with continuous inverse). The map is defined as follows. Consider
the plane in $\mathbb{R}^{3}$ and the $xy$-plane, $\mathbb{R}^{2}.$ For any
point $P$ on the sphere, draw a line in $\mathbb{R}^{3}$ from the north pole
to that point. It will intersect the plane $\mathbb{R}^{2}$ at a point
$P^{\prime}.$ Stereographic projection is the map $P\rightarrow P^{\prime}.$
With some basic geometry, one can explicitly write down the map, which is
\[
\phi\left( x,y,z\right) =\left( \frac{x}{1-z},\frac{y}{1-z}\right) .
\]
The inverse map can also be written explicitly, as
\[
\phi^{-1}\left( x,y\right) =\left( \frac{2x}{x^{2}+y^{2}+1},\frac{2y}%
{x^{2}+y^{2}+1},\frac{x^{2}+y^{2}-1}{x^{2}+y^{2}+1}\right) .
\]
We have the following:
\begin{proposition}
Let $v\in V\left( G\right) $ for a planar graph $G.$ There is a plane graph
representing $G$ such that $v$ is in the boundary of the exterior region.
\end{proposition}
\begin{proof}
Take a plane graph representing $G.$ Map it by inverse stereographic
projection to the sphere. Some region contains $v$ in its boundary. Rotate the
sphere so that a point in that region is at the north pole, then use
stereographic projection to project it back to the plane.
\end{proof}
Recall that our proof of nonembeddability of $K_{3,3}$ and $K_{5}$ used
Euler's theorem, which is essentially a theorem about topology. We can replace
the use of Euler's theorem with a different topological theorem, the Jordan
curve theorem.
\begin{theorem}
[Jordan curve theorem]A Jordan curve is a curve in the plane with no
self-intersection except that it begins and ends at the same point. A Jordan
curve divides the plane into two regions, each of whose boundary is the curve
itself. One region is unbounded, and called the exterior region and the other
is bounded and called the interior region. Any path between the two regions
must intersect the curve.
\end{theorem}
We will not prove the theorem here, but show a quick proof that $K_{5}$ is not embeddable.
Suppose $G$ were a plane curve isomorphic to $K_{5}$ and label the vertices
$V\left( G\right) =\left\{ v_{1},\ldots v_{5}\right\} .$ There is a
subgraph defined by the cycle $C=v_{1},v_{2},v_{3}.$ This cycle must form a
Jordan curve. Thus $v_{4}$ must be either in the interior or exterior regions.
Suppose it is in the interior region. Then We can consider the graph
$G-v_{5},$ which consists of the cycle and some edges inside the cycle. If the
vertex $v_{5}$ is in the exterior region to $C,$ then the edge $v_{4}v_{5}$
must intersect $C,$ a contradiction. Otherwise, $v_{5}$ is inside one of the
cycles $C_{12}=v_{1},v_{2},v_{4},$ $C_{13}=v_{1},v_{3},v_{4},$ or
$C_{23}=v_{2},v_{3},v_{4}.$ Say it is inside $C_{12}.$ Then the edge
$v_{3}v_{5}$ must intersect $C_{12},$ a contradiction. Similar arguments deal
with the remaining cases.
Although $K_{5}$ cannot be embedded in the plane, it can be embedded in the
torus. So can $K_{3,3}.$ They can also be embedded in a Moebius band. Pictures
are courtesy of Wolfram Mathematica,
\url{http://demonstrations.wolfram.com/EmbeddingsOfGraphsInATorusAndInAMoebiusStrip/}.%
%TCIMACRO{\FRAME{dtbpF}{3.7858in}{3.34in}{0pt}{}{}{k5torus.wmf}%
%{\special{ language "Scientific Word"; type "GRAPHIC";
%maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F";
%width 3.7858in; height 3.34in; depth 0pt; original-width 8.1104in;
%original-height 7.1515in; cropleft "0"; croptop "1"; cropright "1";
%cropbottom "0"; filename 'pics/k5torus.wmf';file-properties "XNPEU";}} }%
%BeginExpansion
\begin{center}
\includegraphics[
natheight=7.151500in,
natwidth=8.110400in,
height=3.34in,
width=3.7858in
]%
{pics/k5torus.wmf}%
\end{center}
%EndExpansion%
%TCIMACRO{\FRAME{ftbpF}{3.6189in}{3.193in}{0pt}{}{}{k33torus.wmf}%
%{\special{ language "Scientific Word"; type "GRAPHIC";
%maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F";
%width 3.6189in; height 3.193in; depth 0pt; original-width 8.1104in;
%original-height 7.1515in; cropleft "0"; croptop "1"; cropright "1";
%cropbottom "0"; filename 'pics/k33torus.wmf';file-properties "XNPEU";}} }%
%BeginExpansion
\begin{figure}
[ptb]
\begin{center}
\includegraphics[
natheight=7.151500in,
natwidth=8.110400in,
height=3.193in,
width=3.6189in
]%
{pics/k33torus.wmf}%
\end{center}
\end{figure}
%EndExpansion
%
%TCIMACRO{\FRAME{dtbpF}{3.5359in}{3.1191in}{0pt}{}{}{k5mobius.wmf}%
%{\special{ language "Scientific Word"; type "GRAPHIC";
%maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F";
%width 3.5359in; height 3.1191in; depth 0pt; original-width 8.1104in;
%original-height 7.1515in; cropleft "0"; croptop "1"; cropright "1";
%cropbottom "0"; filename 'pics/k5mobius.wmf';file-properties "XNPEU";}} }%
%BeginExpansion
\begin{center}
\includegraphics[
natheight=7.151500in,
natwidth=8.110400in,
height=3.1191in,
width=3.5359in
]%
{pics/k5mobius.wmf}%
\end{center}
%EndExpansion%
%TCIMACRO{\FRAME{ftbpF}{3.7526in}{3.3109in}{0pt}{}{}{k33mobius.wmf}%
%{\special{ language "Scientific Word"; type "GRAPHIC";
%maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F";
%width 3.7526in; height 3.3109in; depth 0pt; original-width 8.1104in;
%original-height 7.1515in; cropleft "0"; croptop "1"; cropright "1";
%cropbottom "0"; filename 'pics/k33mobius.wmf';file-properties "XNPEU";}} }%
%BeginExpansion
\begin{figure}
[ptbptb]
\begin{center}
\includegraphics[
natheight=7.151500in,
natwidth=8.110400in,
height=3.3109in,
width=3.7526in
]%
{pics/k33mobius.wmf}%
\end{center}
\end{figure}
%EndExpansion
We can now rethink the theorem that $p-q+r=2.$ This is true for plane graphs,
but not for graphs embedded in the torus. The theorem of Euler is that if a
graph divides the torus up into regions each of which is simply connected,
then $p-q+r$ is the same no matter which graph. Simply connected means that
any loop can be deformed into a point. Notice that there are regions of the
torus for which this is not true.
\begin{definition}
A \emph{surface} is a sphere with handles attached. The number of handles is
called the\emph{ genus }of the surface.
\end{definition}
\begin{definition}
An \emph{embedding} of a graph $G$ in a surface is a drawing of $G$ on the
surface with no edge crossings (except at vertices).
\end{definition}
\begin{proposition}
If a graph can be embedded on a surface of genus $g$, then it can be embedded
on a surface of genus $h$ for any $h\geq g$ with no edge crossings.
\end{proposition}
\begin{proof}
Draw the graph on the surface of genus $g,$ then attach handles inside on of
the regions.
\end{proof}
\begin{definition}
The genus of a graph $G$ is the smallest number $g$ such that $G$ can be
embedded in a surface of genus $g$. Planar graphs are graphs of genus $0.$
\end{definition}
\begin{proposition}
Every graph has a genus.
\end{proposition}
\begin{proof}
Draw the graph in the plane (it may have crossings). We can resolve these
crossings by inserting handles where the crossings are, which allow one to
have an overpass so that the two edges no longer cross. This gives one
embedding, and an upper bound on the genus.
\end{proof}
Here are some theorems that we will not prove for now:
\begin{theorem}
$K_{5},K_{6,}K_{7}$ each have genus $1.$ $K_{8}$ has genus $2.$
\end{theorem}
\section{Scheduling problem}
Suppose you wish to assign times for final exams. You should schedule them so
that no student has two exams scheduled at the same time. We can represent
this as a graph, where the vertices are the courses and there is an edge if
any student is taking both courses. We will assign colors to the vertices to
indicate the time of the exam. Clearly, we want adjacent edges to have
different colors. This is called a coloring of the graph.
\begin{definition}
A coloring of a graph $G$ is function $f:V\left( G\right) \rightarrow S,$
for some set $S,$ such that $f\left( v\right) \neq f\left( w\right) $ if
$vw\in E\left( G\right) .$ Often we will choose $S\subset\left\{
1,2,3,\ldots\right\} .$ An $n$-coloring is a coloring where $S$ has $n$ elments.
\end{definition}
\begin{remark}
If $G$ is a $\left( p,q\right) $-graph, then there is always a $p$-coloring.
It is more interesting to find the smallest $n$ for which $G$ has an $n$-coloring.
\end{remark}
\begin{definition}
The chromatic number $\chi\left( G\right) $ is the minimal $n$ such that $G$
has an $n$-coloring.
\end{definition}
Consider $G_{1}$ and $G_{2}$ on C-p. 204. We see that $G_{1}$ has a
5-coloring. However, clearly we can reduce this. We can find a 3-coloring.
However, it does not have a $2$-coloring. Graph $G_{2}$ has a $4$-coloring as
shown. But no $3$-coloring. Thus $\chi\left( G_{1}\right) =3,$ $\chi\left(
G_{2}\right) =4.$ We can also see that graph $H$ on C-p. 205 has $\chi\left(
H\right) =4.$
\begin{proposition}
The minimum number of exam periods is given by the chromatic number of the graph.
\end{proposition}
\begin{proof}
The chromatic number is realized by a coloring of the graph, and on the
coloring, no two classes which share a student have the same time slot
(color). We just need to show that this is the minimal number of exam periods.
Suppose we have an assignment of exam periods which has fewer time slots. Then
these produce an $n$-coloring where $n<\chi\left( G\right) ,$ which is a contradiction.
\end{proof}
Unfortunately, it is generally very difficult to compute a chromatic number.
Here is a result.
\begin{theorem}
Let $\Delta\left( G\right) =\max\left\{ \deg\left( v\right) :v\in
V\left( G\right) \right\} .$ Then
\[
\chi\left( G\right) \leq1+\Delta\left( G\right) .
\]
\end{theorem}
\begin{proof}
Induct on the order of $G.$ Suppose $p=1,$ then $\Delta\left( G\right) =0$
and $\chi\left( G\right) =1.$ This is the base case. For the inductive step,
we assume that $\chi\left( G\right) \leq1+\Delta\left( G\right) $ for any
graph of order $P$ or less. Let $G$ be a graph of order $P+1.$ Let $v$ be a
vertex of maximal degree. $G-v$ has a $\left( 1+\Delta\left( G-v\right)
\right) $-coloring. If $\deg\left( v\right) \leq\Delta\left( G-v\right)
,$ then we have $\Delta\left( G\right) =\Delta\left( G-v\right) ,$ and
furthermore there is a free color to use to color $v$ (since there are
$\Delta\left( G-v\right) +1$ colors available, but only $\Delta\left(
G-v\right) $ vertices adjacent to $v$). If $\deg v>\Delta\left( G-v\right)
,$ then we can introduce a new color and color $v$ with that color.
\end{proof}
Note, that we actually proved something stronger:
\begin{proposition}
$\chi\left( G\right) \leq\min\left\{ 1+\Delta\left( G\right)
,2+\Delta\left( G-v\right) \right\} .$
\end{proposition}
\section{Four color theorem}
Consider a map. We wish to color the map in such a way that adjacent countries
have different colors. The map coloring problem is to find the minimal number
of such colors. This can be translated into the question of finding the
chromatic number of graphs representing the adjacency between countries. The
four color theorem states that
\begin{theorem}
For any planar graph $G,$ $\chi\left( G\right) \leq4.$
\end{theorem}
In other words, we can always color a planar graph with $4$ colors. This
problem has an interesting history. There were a number of false proofs since
the problem began in 1852, proposed by Francis Guthrie in 1858, and told to
the mathematical community some years later by his brother. It was finally
solved by Appel and Haken in 1976. Their proof required a large number of
cases (nearly 2000) that were each checked with a computer. Subsequently, the
number of cases has been reduced to around 600, but still too many for any
person to check by hand. Whether this constituted a proof was extremely
controversial in the mathematics community (and, in some instances, is still controversial).
We will prove that 5 colors is enough, which is much easier.
\begin{lemma}
Every planar graph $G$ contains a vertex $v$ such that $\deg v\leq5.$
\end{lemma}
\begin{proof}
We may assume $G$ has at least $7$ vertices (since otherwise this is obvious).
The sum of all of the degrees of the vertices is equal to $2q.$ If every
vertex has degree larger then or equal to $6,$ then $2q\geq6p.$ On the other
hand, we proved that since $G$ is planar, that $q\leq3p-6.$ Thus we would have
that $6p\leq2q\leq6p-12,$ a contradiction.
\end{proof}
\begin{theorem}
[Five Color Theorem]For any planar graph $G,$ $\chi\left( G\right) \leq5.$
\end{theorem}
\begin{proof}
We induct on the order of the graph $p.$ If $p=1,$ then the chromatic number
is $1.$ Now suppose $\chi\left( G\right) \leq5$ if $p\leq P.$ Let $G$ be a
graph of order $P+1.$ By the lemma, there is a vertex $v$ with $\deg v\leq5.$
By the inductive hypothesis, $G-v$ has a $5$-coloring. If $\deg v<4,$ then we
can easily color $v$ to get a $5$-coloring of $G,$ so we may assume that $\deg
v=5.$ We may number the vertices adjacent to $v$ as $v_{1},v_{2},v_{3}%
,v_{4},v_{5}$ in a cyclical ordering around $v$ (in the plane graph
representation of $G$). If all 5 colors are not represented among the
neighbors of $v,$ then we can produce a $5$-coloring, so we may assume that
$v_{1}$ has color $1,$ $v_{2}$ has color $2,$ etc. We will now consider paths
in $G-v$ with only 2 colors (the colors must alternate because it is a
coloring). First suppose there is no path from $v_{1}$ to $v_{3}$ with only
colors $1$ and $3.$ Consider all paths from $v_{1}$ with only colors $1$ and
$3$ and call this graph $H.$ $H$ is a subgraph of $G-v.$ We can switch all of
the colors in $H$ (1 becomes 3, 3 becomes 1), since any edge from a vertex in
$H$ to a vertex not in $H$ must be between a vertex colored 1 or 3 (in $H$)
and a vertex colored 2, 4,or 5 (not in $H$). Then $v$ has no neighbor colored
1 and so we can color $v$ with $1.$ However, if $v_{3}\in H,$ then switching
the colors would not result in a free color. So, suppose $v_{3}\in H.$ Then
there is a cycle in $G$ given by $P$ followed by $v_{3},v,v_{1}.$ This cycle
has an interior region and an exterior region, and so $v_{2}$ is either in the
interior region or the exterior region and $v_{4}$ is in the other. By the
Jordan curve theorem, any path from $v_{2}$ to $v_{4}$ must cross this cycle,
which means that there is no path from $v_{2}$ to $v_{4}$ with all vertices of
color $2$ or $4.$ Now procede as we did in the case there is no path from
$v_{1}$ to $v_{3}$ with only colors $1$ and $3.$
\end{proof}
There is an alternate proof. Proceed as before until we know we have $v$ with
degree 5. We claim that we can find 2 vertices adjacent to $v$ that are not
adjacent. If not, then there would be a subgraph of $G$ with a subgraph
isomorphic to $K_{5},$ which would mean there is an plane graph isomorphic to
$K_{5}$ (false!). Let $u,w$ be vertices adjacent to $v$ but not adjacent to
each other. We can form a graph from $G-v$ by identifying $u$ and $w,$ and
that graph is planar (we can turn it into a plane graph by deforming $u$ and
$w$ to $v$ along $uv$ and $wv$). Thus there is a $5$-coloring for this graph,
but that gives a $5$-coloring on $G-v$ which has $4$ or fewer colors adjacent
to $v.$
\end{document}