Euler's Theorem for Planar Graphs

== Theorem ==
Let $G = \struct {V, E}$ be a connected planar graph with $V$ vertices and $E$ edges.
Let $F$ be the number of faces of $G$.
Then:
:$V - E + F = 2$
== Proof ==
The proof proceeds by complete induction.
Let $G$ be a planar graph with $V$ vertices and $E$ edges.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:For all planar graphs $G = \struct {V, E}$ such that $V + E = n$, the equation $V - E + F = 2$ holds.
=== Basis for the Induction ===
Let $V + E = 1$.
This is the case of the edgeless graph of order $1$ which consists of a single vertex.
It has exactly one face, which is the entire plane.
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that if $\map P j$ is true, for all $j$ such that $1 \le j \le k$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:For all planar graphs $G = \struct {V, E}$ such that $V + E = k$, the equation $V - E + F = 2$ holds.
from which it is to be shown that:
:For all planar graphs $G = \struct {V, E}$ such that $V + E = {k + 1}$, the equation $V - E + F = 2$ holds.
=== Induction Step ===
This is the induction step:
Let $G$ be a planar graph with $V$ vertices and $E$ edges such that $V + E = k + 1$.
Let $V - E + F = n$
There are a number of cases to consider:
;$(1)$ -- Existence of vertex $v$ of degree $1$
Suppose $G$ has a vertex $v$ of degree $1$.
Then we can remove $v$ and its incident edge.
Let $G' = \struct {V', E'}$ be the (necessarily planar) graph which results from doing this, where $V'$ and $E'$ are the vertices and edges of $G'$.
The number of faces of $G'$ is the same as the number of faces of $G$, as the removed edges does not separate the two faces, but instead juts out into the one face.
So:
:$V' = V - 1$ (as we have removed $1$ vertex)
:$E' = E - 1$ (as we have removed $1$ edges).
Thus we have:
But:
:$V' + E' = V + E - 2 = k - 1$
and so by the induction hypothesis:
:$V' - E' + F = 2$
It follows that:
:$V - E + F = 2$
;$(2)$ -- Existence of a loop
Suppose $G$ has a loop $e$.
Then we can remove $e$.
Let $G' = \struct {V', E'}$ be the (necessarily planar) graph which results from doing this, where $V'$ and $E'$ are the vertices and edges of $G'$.
Let $F'$ be the number of faces of $G'$.
Then $F'$ one less than the number of faces of $G$, as the removal of $e$ has caused the face enclosed by $e$ to be merged with the face on the other side of $e$.
So:
:$V' = V$ (as we have not changed any vertices)
:$E' = E - 1$ (as we have removed $1$ edge).
:$F' = F - 1$ (as we have merged $2$ faces into $1$).
Thus we have:
But:
:$V' + E' = V + E - 1 = k$
and so by the induction hypothesis:
:$V' - E' + F' = 2$
It follows that:
:$V - E + F = 2$
;$(3)$ -- Existence of vertex $v$ of degree $2$
Suppose $G$ has:
:neither a vertex of degree $1$
:or a loop
but does have a vertex $v$ of degree $2$ such that $v$ is not either end of a loop.
Then we can remove $v$ and replace its two incident edges with a single edge.
Let $G' = \struct {V', E'}$ be the (necessarily planar) graph which results from doing this, where $V'$ and $E'$ are the vertices and edges of $G'$.
The number of faces of $G'$ is the same as the number of faces of $G$ as the two edges that were replaced with a single edge separate the same two faces.
So:
:$V' = V - 1$ (as we have removed $1$ vertex)
:$E' = E - 1$ (as we have replaced $2$ edges with $1$ edge).
Thus we have:
But:
:$V' + E' = V + E - 2 = k - 1$
and so by the induction hypothesis:
:$V' - E' + F = 2$
It follows that:
:$V - E + F = 2$
;$(3)$ -- Existence of vertex $v$ of degree $m$ where $m > 2$
Suppose $G$ has:
:no vertex of degree $1$
:no loop
:no vertex of degree $2$
Then all vertices of $G$ will be of degree $m$ where $m > 2$.
Let $u$ and $v$ be two adjacent vertices of $G$ which is not a bridge.
Let $e$ be the edge which is incident to both $u$ and $v$.
Let $G' = \struct {V', E'}$ be the (necessarily planar) graph which results from removing $e$, where $V'$ and $E'$ are the vertices and edges of $G'$.
Let $F'$ be the number of faces of $G'$.
Then $F'$ one less than the number of faces of $G$, as the removal of $e$ has caused the faces separated by $e$ to be merged with the face on the other side of $e$.
By construction, $E' = E - 1$.
Removing $e$ will not affect the number of vertices of $G$, so $V' = V$.
So:
:$V' = V$ (as we have removed $1$ vertex)
:$E' = E - 1$ (as we have removed $1$ edges).
:$F' = F - 1$ (as we have merged $2$ faces into $1$).
Thus we have:
But:
:$V' + E' = V + E - 1 = k$
and so by the induction hypothesis:
:$V' - E' + F' = 2$
It follows that:
:$V - E + F = 2$
All cases have been covered.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
== Sources ==
* 
* 
Category:Euler's Theorems
Category:Planar Graphs