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

.
Proof. We prove by induction on the number of regions.

- 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.

Therefore, if the number of edges on the boundary of a region is summed over all regions, the result is 3r.

On the other hand, such a sum counts each edge twice, so .

Applying the Euler's formula, we obtain the desired result:

and so

.

Corollary 7.4. If G is a planar graph of order and size m, then .


Proof.

Let G be a planar graph of order n and size m with .

- 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.

 

Figure 7.3. A polyhedron and its associated planar graph

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 .

Assume now that and the assertion holds for .

 

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.8. The complete graph is not planar.

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 .