Euler's Theorem for Planar Graphs

From ProofWiki
Jump to navigation Jump to search

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.


\(\ds V\) \(=\) \(\ds 1\)
\(\ds E\) \(=\) \(\ds 0\)
\(\ds F\) \(=\) \(\ds 1\)
\(\ds \leadsto \ \ \) \(\ds V - E + F\) \(=\) \(\ds 2\)

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:

\(\ds V - E + F\) \(=\) \(\ds \paren {V' + 1} - \paren {E' + 1} + F\)
\(\ds \) \(=\) \(\ds V' + 1 - E' - 1 + F\)
\(\ds \) \(=\) \(\ds V' - E' + F\)

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$

$\Box$


$(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:

\(\ds V - E + F\) \(=\) \(\ds V' - \paren {E' + 1} + \paren {F' + 1}\)
\(\ds \) \(=\) \(\ds V' - E' - 1 + F + 1\)
\(\ds \) \(=\) \(\ds V' - E' + F'\)

But:

$V' + E' = V + E - 1 = k$

and so by the induction hypothesis:

$V' - E' + F' = 2$

It follows that:

$V - E + F = 2$

$\Box$


$(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:

\(\ds V - E + F\) \(=\) \(\ds \paren {V' + 1} - \paren {E' + 1} + F\)
\(\ds \) \(=\) \(\ds V' + 1 - E' - 1 + F\)
\(\ds \) \(=\) \(\ds V' - E' + F\)

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$

$\Box$


$(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:

\(\ds V - E + F\) \(=\) \(\ds V' - \paren {E' + 1} + \paren {F' + 1}\)
\(\ds \) \(=\) \(\ds V' - E' - 1 + F + 1\)
\(\ds \) \(=\) \(\ds V' - E' + F'\)

But:

$V' + E' = V + E - 1 = k$

and so by the induction hypothesis:

$V' - E' + F' = 2$

It follows that:

$V - E + F = 2$

$\Box$


All cases have been covered.


So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.

$\blacksquare$


Although this article appears correct, it's inelegant. There has to be a better way of doing it.
In particular: clumsy and handwavey
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by redesigning it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Improve}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Source of Name

This entry was named for Leonhard Paul Euler.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Euler%27s_Theorem_for_Planar_Graphs&oldid=611759"