7.2. The Euler's formula and its consequences.
Theorem 7.1. (Euler's formula): If a connected plane graph G has n vertices, m edges and r regions, then

-
If then G
does not contain a cycle so it is a tree and the result holds.
-
Suppose that and the result holds for any
. Since
, so G contains at least one cycle.
Let ab
be an edge in a cycle, and suppose that ab is in the boundary of two
regions, say . Omitting ab, in the new graph G' we get
. Therefore
.
Corollary 7.2. If G is a plane graph with n vertices, m edges and r regions, then
.
Theorem 7.3. If G is maximal planar
graph of order and size m, then
.
Proof.
Let G be a maximal planar graph with r regions.
The boundary of every region is a triangle, and each edge is on the boundary of two regions.

Figure 7.2. A maximal planar graph with r = 4.
On the other
hand, such a sum counts each edge twice, so .
Applying the Euler's formula, we obtain the desired result:
and so
.


Proof.

- If then the result is obvious.
- Suppose . The
implies that
Assume that all vertices have degree at least 6.
Then which contradicts the above formel.
So, G contains a vertex of degree 5 or less.
Corollary 7.5. In a maximal planar graph of order at least 4 the minimum degree is at least 3.
Proof.
Let us consider a maximal planar graph G with order size m. Then, by Theorem 7.3,
we know that
.
- It is trivial, that G does not contain vertices with degree 0 or 1.
- We will show that G contains no vertex of
degree 2. Suppose the contrary,
and let for which
.
Then is a planar graph of order
and size
.
Since , then for the graph
we get
,
which contradicts Corollary 7.4.
Is there any connection between planar graphs and polyhedra?
Every polyhedron P is associated a connected planar graph , whose vertices and edges are the vertices and
edges of P.
If is a plane graph, then the faces of P
are the regions of
and every edge of
is on the boundary of two regions.

Theorem 7.6. (Euler's Polyhedron formula): If V, E and F denote the number of vertices, edges and faces of a polyhedron, respectively, then

When will be a graph G a planar-graph? The Euler's formula is only necessary but not sufficient.
The Euler's formula gives an upper bound for
the number of edges of a planar graph :
.
So, a planar graph may not contain "too many" edges. If we introduce the definition of the girth, then we can improve the upper bound.
The girth is the number of edges in a shortest cycle. (The girth in an acyclic graph is ∞. )
Theorem 7.7. A planar graph of order n and girth at least , has size at most
.
Proof. Let be a planar
graph with girth at least g.
If then G
is acyclic so
.


First we suppose that G
contains a bridge. If ab is a bridge then is the union of
two vertex disjoint subgraphs, say
and
. Let
and
. Because of the induction hypothesis for the two
disconnected subgraph the assertion is valid, so
If G is bridgless, then we get
Using the Euler's formula
So

Corollary 7.9. The complete bipartite graph is
not planar.
A graph H is the subdivision of the graph G if we substitute an edge with a path which joins to the edge only in its endvertices.
Theorem
7.10. (Kuratowski 1930): A graph is planar iff it does not contain a subdivision
of or
.