15.2: Euler’s Formula

Euler came up with a formula that holds true for any planar embedding of a connected graph.

Theorem \(\PageIndex{1}\)

If \(G\) is a planar embedding of a connected graph (or multigraph, with or without loops), then

\[|V | − |E| + |F| = 2.\]

Proof 1:

We will prove this formula by induction on the number of faces of the embedding. Let \(G\) be a planar embedding of a connected graph (or multigraph, with or without loops).

Base case: If \(|F| = 1\) then \(G\) cannot have any cycles (otherwise the interior and exterior of the cycle would be \(2\) distinct faces). So \(G\) must be a connected graph that has no cycles, i.e., a tree. By Theorem 12.4.1 we know that we must have \(|E| = |V | − 1\), so

\[|V | − |E| + |F| = |V | − (|V | − 1) + 1 = 2.\]

A tree cannot have any loops or multiple edges, as these form cycles.

Inductive step: We begin by stating our inductive hypothesis. Let \(k ≥ 1\) be arbitrary, and assume that for any planar embedding of a connected graph (or multigraph, with or without loops) with \(k\) faces, \(|V | − |E| + |F| = 2\).

Let \(G\) be a planar embedding of a connected graph with \(k + 1 ≥ 2\) faces. Since trees have only one face, \(G\) must have a cycle. Choose any edge \(e\) that is in a cycle of \(G\), and let \(H = G \setminus \{e\}\). Clearly, we have

\[|E(H)| = |E(G)| − 1\]

and \(|V (H)| = |V (G)|\). Also,

\[|F(H)| = |F(G)| − 1 = k\]

since the edge \(e\) being part of a cycle must separate two faces of \(G\), which are united into one face of \(H\). Furthermore, since \(e\) was in a cycle and \(G\) is connected, by Proposition 12.3.4, \(H\) is connected, and \(H\) has a planar embedding induced by the planar embedding of \(G\). Therefore our inductive hypothesis applies to \(H\), so

\[ \begin{equation} \begin{split} 2 &= |V (H)| − |E(H)| + |F(H)| \\ &= |V (G)| − (|E(G) − 1) + (|F(G)| − 1) \\ &= |V (G)| − |E(G)| + |F(G)| \end{split} \end{equation} \]

This completes the inductive step.

By the Principle of Mathematical Induction, \(|V | − |E| + |F| = 2\) for any planar embedding of a connected graph (or multigraph, with or without loops).

The above proof is unusual for a proof by induction on graphs, because the induction is not on the number of vertices. If you try to prove Euler’s formula by induction on the number of vertices, deleting a vertex might disconnect the graph, which would mean the induction hypothesis doesn’t apply to the resulting graph.

However, there is a different graph operation that reduces the number of vertices by \(1\), and keeps the graph connected. Unfortunately, it may turn a graph into a multigraph, so it can only be used to prove a result that holds true for multigraphs as well as for graphs. This operation is called edge contraction.

Definition: Contracting the Edge

Let \(G\) be a graph with an edge \(uv\). The graph \(G'\) obtained by contracting the edge \(uv\) has vertices.

\[V (G' ) = (V (G) \setminus \{u, v\}) ∪ \{u' \},\]

where \(u'\) is a new vertex. The edges are

\[E(G') = \left( [E(G) \setminus \{ux : ux ∈ E(G)\}] \setminus \{vx : vx ∈ E(G)\} \right) ∪ \{u'y | uy ∈ E(G) \text{ or } vy ∈ E(G)\}\]

If you think of vertices \(u\) and \(v\) as being connected by a very short elastic that has been stretched out in \(G\), then you can think of \(G'\) as the graph you get if you allow the elastic to contract, combining the vertices \(u\) and \(v\) into a “new” vertex \(u'\).

Notice that if \(G\) is connected, then the graph obtained by contracting any edge of \(G\) will also be connected. However, if \(uv\) is the edge that we contract, and \(u\) and \(v\) have a mutual neighbour \(x\), then in the graph obtained by contracting \(uv\), there will be a multiple edge between \(u'\) and \(x\). Also, if \(G\) has a planar embedding, then after contracting any edge there will still be a planar embedding. If \(u \neq v\), then contracting \(uv\) reduces the number of vertices by one, reduces the number of edges by one, and does not change the number of faces.

Now we can use this operation to prove Euler’s formula by induction on the number of vertices

Theorem \(\PageIndex{1}\)

If \(G\) is a planar embedding of a connected graph (or multigraph, with or without loops), then

\[|V | − |E| + |F| = 2.\]

Proof 2:

Let \(G\) be a planar embedding of a connected graph (or multigraph, with or without loops).

Base case: If \(|V | = 1\) then \(G\) has one vertex. Furthermore, every edge is a loop. Every loop involves \(1\) edge, and encloses \(1\) face. This graph will therefore have one more face than it has loops (since it has one face even if there are no loops). Thus,

\[|V | − |E| + |F| = 1 − e + (e + 1) = 2.\]

Inductive step: We begin by stating our inductive hypothesis. Let \(k ≥ 1\) be arbitrary, and assume that for any planar embedding of a connected graph (or multigraph, with or without loops) with \(k\) vertices, \(|V | − |E| + |F| = 2\).

Let \(G\) be a planar embedding of a connected graph with \(k + 1 ≥ 2\) vertices. Since the graph is connected and has at least two vertices, it has at least one edge \(uv\), with \(u \neq v\). Let \(G'\) be the graph we obtain by contracting \(uv\). Then \(G'\) is a planar embedding of a connected graph (or multigraph, with or without loops) on \(k\) vertices, so our inductive hypothesis applies to \(G'\). Therefore,

\[ \begin{equation} \begin{split} 2 &= |V (G')| − |E(G')| + |F(G')| \\ &= (|V (G)| − 1) − (|E(G) − 1) + |F(G)| \\ &= |V (G)| − |E(G) + |F(G)| \end{split} \end{equation} \]

This completes the inductive step.

By the Principle of Mathematical Induction, \(|V | − |E| + |F| = 2\) for any planar embedding of a connected graph (or multigraph, with or without loops).

Contraction of edges has some other very important uses in graph theory. Before looking at some corollaries of Euler’s Formula, we’ll explain one well-known theorem that involves edge contraction and planar graphs.

Definition: Minor

Let \(G\) be a graph. Then \(H\) is a minor of \(G\) if we can construct \(H\) from\(G\) by deleting or contracting edges and deleting vertices.

In 1937, Wagner proved a theorem quite similar to Kuratowski’s.

Theorem \(\PageIndex{2}\): Wagner's Theorem

A graph is planar if and only if it has no minor isomorphic to \(K_5\) or \(K_{3,3}\).

It is possible to prove Wagner’s Theorem as an easy consequence of Kuratowski’s Theorem, since if \(G\) has a subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\) then contracting all but one piece of each subdivided edge gives us a minor that is isomorphic to \(K_5\) or \(K_{3,3}\). Nonetheless, Wagner’s Theorem is important in its own right, as the first example of the much more recent and very powerful work by Neil Robertson and Paul Seymour on graph minors.

A family is said to be minor-closed if given any graph in the family, any minor of the graph is also in the family. Planar graphs are an example of a minor-closed family, since the operations of deletion (of edges or vertices) and contraction of edges preserve a planar embedding. Robertson and Seymour proved the remarkable result that if a family of graphs is minor-closed, then the family can be characterised by a finite set of “forbidden minors.” That is, for any such family \(\mathcal{F}\), there is a finite set \(\mathcal{L}\) of graphs, such that \(\mathcal{G} ∈ \mathcal{F}\) if and only if no minor of \(\mathcal{G}\) appears in \(\mathcal{L}\). Wagner’s Theorem tells us that when \(\mathcal{F}\) is the family of planar graphs, \(\mathcal{L} = \{K_5, K_{3,3}\}\).

Euler’s Formula has some important corollaries.

Corollary \(\PageIndex{1}\)

Let \(G\) be a connected graph. Then every planar embedding of \(G\) has the same number of faces.

Proof

We have \(|V | − |E| + |F| = 2\). Since \(|V|\) and \(|E|\) do not depend on the choice of embedding, we have \(|F| = 2 + |E| − |V|\) cannot depend on the choice of embedding.

Corollary \(\PageIndex{2}\)

If \(G\) is a simple connected planar graph and \(|V| ≥ 3\), then

\[|E| ≤ 3|V| − 6\]

If in addition, \(G\) has no cycles of length less than \(4\), then \(|E| ≤ 2|V| − 4\).

Proof

Fix a planar embedding of \(G\). We move around each face, counting the number of edges that we encounter, and work out the result in two ways.

First, we look at every face in turn and count how many edges surround that face. Since the graph is simple, every face must be surrounded by at least \(3\) edges unless there is only one face. If there is only one face and when moving around this face we do not count at least \(3\) edges, then the graph is a tree that has at most one edge, so \(|V| ≤ 2\). Therefore, our count will come to at least \(3|F|\).

Every edge either separates two faces, or dangles into a face. In the former case, it will be counted once each time we move around one of the two incident faces. In the latter case, it will be counted twice as we move around the face it dangles into: once when we move inwards along this dangling part, and once when we move back outward. Thus, every edge is counted exactly twice, so our count will come to exactly \(2|E|\).

Combining these, we see that \(2|E| ≥ 3|F|\), so \(|F| ≤ \dfrac{2|E|}{3}\). If \(G\) has no cycles of length less than \(4\), then every face must be surrounded by at least \(4\) edges, so the same argument gives \(2|E| ≥ 4|F|\), so \(|F| ≤ \dfrac{|E|}{2}\).

By Euler’s Formula, \(|V| − |E| + |F| = 2\), so

\[|V| − |E| + \dfrac{2|E|}{3} ≥ 2.\]

Multiplying through by \(3\) and moving the \(|E|\) terms to the right-hand side, gives

\[3|V| ≥ |E| + 6,\]

which can easily be rearranged into the form of our original statement. In the case where \(G\) has no cycles of length less than \(4\), we obtain instead

\[|V| − |E| + \dfrac{|E|}{2} ≥ 2,\]

so \(2|V| ≥ |E| + 4\), which again can easily be rearranged into the form given in the statement of this corollary.

Corollary \(\PageIndex{3}\)

If \(G\) is a simple connected planar graph, then \(δ(G) ≤ 5\).

Proof

Towards a contradiction, suppose that \(G\) is a simple connected planar graph, and for every \(v ∈ V\), \(d(v) ≥ 6\). Then

\[\sum_{v∈V} d(v) ≥ 6|V|.\]

By Euler’s handshaking lemma, this gives

\[\sum_{v∈V} d(v) = 2|E| ≥ 6|V |.\]

Therefore,

\[|E| ≥ 3|V | > 3|V | − 6,\]

but this contradicts Corollary 15.2.2.

Euler’s Formula (and its corollaries) give us a much easier way to prove that \(K_5\) and \(K_{3,3}\) are non-planar.

Corollary \(\PageIndex{4}\)

The graph \(K_5\) is not planar.

Proof

In \(K_5\) we have \(|E| = \binom{5}{2} = 10\), and \(|V| = 5\). So,

\[3|V| − 6 = 15 − 6 = 9 < 10 = |E|\]

By Corollary 15.2.2, \(K_5\) must not be planar.

Corollary \(\PageIndex{5}\)

The graph \(K_{3,3}\) is not planar

Proof

In \(K_{3,3}\) we have \(|E| = 9\), and \(|V| = 6\). So,

\[2|V | − 4 = 12 − 4 = 8 < 9 = |E|\]

Since \(K_{3,3}\) is bipartite, it has no cycles of length less than \(4\), so by Corollary 15.2.2, \(K_{3,3}\) must not be planar

Exercise \(\PageIndex{1}\)

1) Use induction to prove an Euler-like formula for planar graphs that have exactly two connected components.

2) Euler’s formula can be generalised to disconnected graphs, but has an extra variable for the number of connected components of the graph. Guess what this formula will be, and use induction to prove your answer.

3) Find and prove a corollary to Euler’s formula for disconnected graphs, similar to Corollary 15.2.2. (Use your answer to question \(2\).)

4) For graphs embedded on a torus, \(|V| − |E| + |F|\) has a different (but constant) value, as long as all of the faces “look like” discs. (If you are familiar with topology, the faces must be embeddable into a plane, rather than looking like a torus. So putting a planar embedding of a graph down on one side of a torus doesn’t count.) What is this value?

5) Definition. We say that a planar embedding of a graph is self-dual if it is isomorphic to its planar dual. Prove that if a planar embedding of the connected graph \(G\) is self-dual, then \(|E| = 2|V| − 2\).

6) Definition. The complement of \(G\) is the graph with the same vertices as \(G\), but whose edges are precisely the non-edges of \(G\). (That is, \(u\) is adjacent to \(v\) in the complement of \(G\) if and only \(u\) is not adjacent to \(v\) in \(G\).) Therefore, if \(G^c\) is the complement of \(G\), then \(E(K_{|V(G)|})\) is the disjoint union of \(E(G)\) and \(E(G^c)\). Show that if \(G\) is a simple planar graph with at least eleven vertices, then the complement of \(G\) is not planar.

7) Find a planar graph \(G\) with \(|V| = 8\) whose complement is also planar.

8) For each of the following sets of conditions, either draw a connected, simple graph \(G\) in the plane that satisfies the conditions, or explain how you know that there isn’t one.

(a) The graph has \(15\) vertices and \(12\) edges.

(b) The graph has \(10\) vertices and \(33\) edges.

(c) The graph has \(5\) vertices and \(8\) edges.

(d) The graph has \(6\) vertices and \(9\) edges, and the embedding has 6 faces