Chapter 5c


Planarity and the Paris Metro


Technical Terms:

planar, regular polyhedron, Platonic solid, Schlegel diagram, Schläfli symbol, regular graph, tetrahedron, cube, octahedron, dodecahedron, icosahedron, loop, stereographic projection, embed, component, union, homeomorphism, cycle, adjacent, subgraph

Link to Chapter 5.


Planarity

The idea of planarity in fact has its roots in spherical geometry. A regular polyhedron is called a Platonic solid. The question was: which Platonic solids exist (Coxeter, 1961)? Since the surface of a 3-dimensional solid is 2-dimensional, this essentially becomes a planar question: when can the plane representation of a regular polyhedron (called its Schlegel diagram) be drawn in the plane without edges crossing each other. Surprisingly, the answer lies in numerical properties of the numbers of nodes, edges, and faces of this Schlegel diagram.

The chapter will proceed in five pieces.

  1. First, the general theorem for planar graphs (not just Schlegel diagrams) will be stated.
  2. Next, the theorem will be applied to solve the Platonic solid problem.
  3. Third, the general theorem will be proved, along with some corollaries which will be useful.
  4. It will be shown, first using the corollaries and next using the Jordan Curve Theorem, that K5 and K3,3 are non-planar graphs.
  5. Finally, it will be shown that all non-planar graphs contain some subgraph that looks like K5 or K3,3.

Theorem 5c.1. (Euler's Formula). Let G be a connected planar graph (loops and multiple edges allowed). Suppose G has v nodes, e edges, and f faces. Then v = e - f + 2.

This theorem is essential to the study of planarity and in fact was known in its classical context long before graph theory existed as a separate discipline of mathematics (Hilbert and Cohn-Vossen).

Before proving the theorem, we first apply it to the Platonic solid case. A Platonic solid has Schläfli symbol {p,q} if its faces are regular p-gons, and q of these faces meet at each node. As noted before, a plane representation of such a solid by a planar graph (which is of course regular of degree q) is called its Schlegel diagram.

Five well-known Platonic solids, even in ancient times were the cube, tetrahedron, octahedron, dodecahedron, and icosahedron. They are illustrated below.

The cube (Schläfli symbol {4,3}) has 6 square faces, 3 of which meet at each of its 8 nodes. Thus, there are 12 edges (half of 8 times 3). Note that v = e - f + 2 [8 = 12 - 6 + 2]. Its Schlegel diagram is shown below (Figure 5c.1).

Image

Figure 5c.1. This figure shows a Schlegel diagram of the cube.

Five faces are easily visible in the diagram. The sixth is the rest of the plane. Thus, the four outer edges are the boundary of the sixth face, just as they are the boundary edges of the "bottom" face of the three dimensional cube we are "viewing" from above.

The tetrahedron ({3,3}) has 4 cubic faces, 3 of which meet at each of its 4 nodes. This "pyramid" with triangular base has 6 edges [4 = 6 - 4 + 2]. Its Schlegel diagram is shown below (Figure 5c.2).

Image

Figure 5c.2. This figure shows a Schlegel diagram of the tetrahedron.

The octahedron ({3,4}) has 8 cubic faces, 4 meeting at each of its 6 nodes. Thus there are 12 edges [6 = 12 - 8 + 2]. Its Schlegel diagram is shown below (Figure 5c.3).

Image

Figure 5c.3. This figure shows a Schlegel diagram of the octahedron.

The dodecahedron ({5,3}) has 12 pentagonal faces, 3 of which meet at each of its 20 nodes. Thus there are 30 edges [20 = 30 - 12 + 2]. Its Schlegel diagram is shown below (Figure 5c.4).

Image

Figure 5c.4. This figure shows a Schlegel diagram of the dodecahedron.

The icosahedron ({3,5}) has 20 triangular faces, 5 of which meet at each of its 12 nodes. Thus there are 30 edges [ 12 = 30 - 20 + 2]. Its Schlegel diagram is shown below (Figure 5c.5).

Image

Figure 5c.5. This figure shows a Schlegel diagram of the icosahedron.

All of these have long since been shown to be geometrically realizable in 3-space. We shall show there can be no others. (Note that to make geometric sense p ≥ 3 and q ≥ 3.) From the theorem that the sum of the degrees of the nodes is twice the number of edges in any graph, we obtain 2e = qv in any Platonic solid. Since there are p edges on each face, and each edge is part of 2 faces, it is also true that 2e = pf.

Thus the equation v - e + f = 2 becomes 2e/q - e + 2e/p = 2 or e((2p + 2q -pq)/pq) = 2.

Since e, p, q are all positive, this says

2p + 2q - pq > 0

pq - 2p - 2q < 0

pq - 2p - 2q + 4 < 4

(p - 2)(q - 2) < 4.

The only positive integer solutions of this equation are the following solutions, corresponding to the five Platonic solids above.

p = 4,   q = 3

p = 3,   q = 3

p = 3,   q = 4

p = 5,   q = 3

p = 3,   q = 5

Thus, the truth of Euler's formula assures the fact that there are exactly five Platonic solids. We move now to the proof of its truth.

The proof of Euler's formula follows. The proof is by mathematical induction on the number of edges.

Basis Step Suppose e = 1. There are only two possibilities (one if we disallow loops). G could be as below.

ImageorImage

v = 2                            v = 1

e = 1                            e = 1

f = 1                             f = 2

v - e + f = 2                 v - e + f = 2

Inductive Step Suppose now that Euler's formula holds for graphs with fewer than e edges, and suppose that G is a connected planar graph with e edges, v nodes, and f faces. There are two cases.

Case 1. Suppose G contains no circuits. Then G is a tree, f = 1, and G has a vertex of degree 1. Remove that vertex and its incident edge to obtain a new graph G' with e' = e - 1 edges, v' = v - 1 nodes, and f' = f = 1 faces. By induction

v' = e' - f' +2

or   v - 1 = e - 1 - f + 2

or        v = e - f + 2.

Thus, G satisfies Euler's formula.

Case 2. Suppose G contains a circuit. Remove an edge from that circuit to obtain a new graph G' with e' = e - 1 edges, v' = v nodes, and f' = f - 1 edges. By induction

v' = e' - f' + 2

or    v = (e - a) - (f - 1) + 2

or    v = e - f + 2.

Again, G satisfies Euler's formula.

Consideration of some simple special cases leads to some simple corollaries.

Corollary 5c.1. If G has no loops, then the following inequality holds: e ≤ 3v - 6.

Proof: Since G has no loops, each face is at least a triangle and so bounded by at least 3 edges. Since each edge is on 2 faces, this guarantees 2e ≥ 3f. (Recall that in the tetrahedron, octahedron, and icosahedron, which had all faces triangular, we had 2e = 3f.) Since

f = e - v +2

3f = 3e - 3v + 6 ≤ 2e

Thus,  e ≤ 3v - 6.

Corollary 5c.2. If G has neither loops nor triangles, then the following inequality holds: e ≤ 2v - 4.

Proof: Now each face is bounded by at least 4 edges, so 2e ≥ 4f or 2f e.

By Euler’s formula, f = e - v + 2 and 2f = 2e - 2v + 4 ≤ e; thus, e ≤ 2v - 4.

Therefore, by Corollary 5c.1, a connected planar graph with no loops and 5 nodes can have at most 3(5) - 6 = 9 edges. Hence, K5, with its 10 edges, is non-planar. Similarly, by Corollary 5c.2, a connected planar graph with neither loops nor triangles and 6 nodes can have at most 2(6) - 4 = 8 edges. K3,3, being bipartite, has no triangles. Since it has 9>8 edges, it is also non-planar.

Both these demonstrations of non-planarity depended on Euler's formula. But the non-planarity of K5 and K3,3 can also be demonstrated directly, using the Jordan Curve Theorem, which says that any simple closed curve in the plane divides the plane into two regions, and one cannot get from one region to the other without crossing the curve.

Demonstration 1 K5 is non-planar.

Suppose the contrary. Let the nodes of K5 be A, B, C, D, E. Then ABCDEA is a pentagon in the plane (Figure 5c.6).

Image

Figure 5c.6. 

BE must be either inside or outside the pentagon. Without loss of generality, assume it is inside. Then, to avoid crossings, AC and AD must be outside the pentagon. Thus, we have reached the situation shown in Figure 5c.6. Now BD and CE must both be inside BCDE and hence must cross.

Demonstration 2 K3,3 is non-planar.

Suppose the contrary. Let the nodes of K3,3 be A, B, C (one part) and X, Y, Z (the other part). Then the circuit A, X, B, Y, C, Z, A must be a planar hexagon (Figure 5c.7).

Image

Figure 5c.7.

Then at least two of AY, BZ, and CX must be either inside or outside the hexagon (again assume inside without loss of generality). Hence, they must cross.

Kasimir Kuratowski demonstrated that all non-planar graphs contain (essentially) a K5 or a K3,3. We conclude this chapter with a proof of Kuratowski's Theorem.

Kuratowski's Theorem

First, note a simple fact about plane graphs.

Theorem 5c.2. A plane graph may be embedded in the plane so that any given face is the exterior.

Proof: Let G be a plane graph, f the face in question. Using inverse stereographic projection, embed G on the sphere. Rotate the sphere so that f contains the North Pole. Now use stereographic projection to embed G on the plane with f the exterior face.

Two graphs are said to be homeomorphic if one can be obtained from the other by a sequence of subdivisions of edges by insertion of a node along the edges, forming two edges where there was one. For example, any two paths are homeomorphic.

Theorem 5c.3. (Kuratowski's Theorem). A graph G is planar if and only if it has no subgraph homeomorphic to K5 or K3,3.

Proof: (Dirac and Schuster, 1954).

⇐ If G is planar, it clearly cannot have a subgraph homeomorphic to K5 or K3,3, from above.

⇒ So suppose G is not planar. Assume the theorem is false, and pick a counterexample G with the minimum number of lines and no subgraph homeomorphic to K5 or K3,3 . G contains no node of degree 1, or removing it would give a smaller counterexample. It contains no node of degree 2, for if v were of degree 2, adjacent to u and w, replacing the path u, v, w by a new edge u, w (removing v) would give a smaller counterexample. Hence, every node of G has degree at least three.

Similarly, G must be connected. Otherwise, any non-planar component would be smaller. In fact, G must be a block. Otherwise, at least one of the blocks of G would be non-planar, or their union would be planar. Therefore, the non-planar block would be a smaller counterexample.

Let e = uv be an arbitrary edge of G. Then H = G - e must be planar.

Lemma 5c.3.1. There is a cycle in H containing u and v.

Proof: Suppose not. Then, by Theorem 4c.3, u and v lie in different blocks of H. So there is a cutnode w lying on every u - v path of H. Form the graph H0 = H wu wv; u and v still lie in different blocks of H0 . Call them B1 and B2; both contain the node w. Each of B1 and B2 has fewer edges than G. Suppose B1 were non-planar. By minimality, B1 would have to contain a subgraph homeomorphic to K5 or K3,3. But then the subgraph of G obtained by replacing wu by a path from u to w beginning with e would be homeomorphic to K5 or K3,3, a contradiction. Therefore, B1 is planar. Similarly, B2 is planar. Moreover, by Theorem 5c.2, B1 and B2 can be drawn in the plane with wu and wv bounding the exterior region. Hence, H0 can be embedded in the plane with both wu and wv on the exterior region. Then e = uv cannot destroy the planarity of H0 by being added to it. Hence G, being a subgraph of H0 e, is planar, a contradiction. (End proof of Lemma.)


Now let H be embedded in the plane in such a way that some cycle C containing u and v has a maximum number of regions interior to it. Give C an orientation in a cyclic order. Let C[s,t] denote the oriented path from s to t along C. If t does not immediately follow s on C, let C(s,t) denote the subpath of C[s,t] obtained by removing u and v. Since C is oriented, it has an interior and an exterior (by Jordan's Curve Theorem); specifically, by the exterior of C we mean the subgraph of H induced by the nodes lying outside C; the components of the subgraph are called exterior components of C. By an outer piece of C is meant a connected subgraph of H induced either by all edges incident with at least one node in some exterior component or by an edge exterior to C which meets two vertices of C. The interior of C, an interior component, and an inner piece are defined similarly.

An outer or inner piece is called s - t separating if it meets both C(s,t) and C(t,s). Clearly, an outer or inner piece cannot be s - t separating if s and t are adjacent on C. Since H is connected, each outer piece must meet C. Since H has no cutnodes, each outer piece must have at least two nodes in common with C.

No outer piece can meet C(u,v) or C(v,u) in more than one node, or there would exist a cycle containing u and v with more interior regions than C. Similarly, no outer piece can meet u or v. Hence every outer piece meets C in exactly two nodes and is u - v separating. Moreover, since e cannot be added to H to create a planar graph, there must be a u - v separating inner piece.

Lemma 5c.3.2. There exists a u - v separating piece (call the node where it meets C(u,v) u1 and the node where it meets C(v,u) v1) such that there is an inner piece which is both u - v separating and u1 - v1 separating.

Proof: Suppose not. Then label the u - v separating inner pieces I1, I2, ... according to which is first encountered while moving along C from u.

Let u2 and u3 be the first and last nodes of I1 meeting C(u,v), and let v2 and v3 be the first and last nodes of I1 meeting C(v,u) (u2 = u3, v2 = v3 are possible). Figure 5c.8 illustrates the situation.

Image

Figure 5c.8. Orientation is clockwise around the geometric circle representing the graphical cycle, labeled C in the text.

If the Lemma is false, every outer piece necessarily has both its common nodes in C(v3,u2) or C(u3,v2), since otherwise there would exist an outer piece meeting C(u,v) at u1 and C(v,u) at v1 (as illustrated in red on Figure 5c.8), and I1 would be both u - v separating and u1 - v1 separating.

Then a curve C1 joining v3 and u2 can be drawn in the exterior region meeting no edge of H. Thus, all of I1 can be transferred outside C1 in a planar fashion. This can be done for each inner piece if the Lemma is false. But then e = uv can be drawn in a planar fashion inside C, a contradiction to the non-planarity of G. (End proof of Lemma.)


It now remains to prove the Theorem. Let J be the inner piece guaranteed by Lemma 5c.3.2, which is both u - v separating and u1 - v1 separating.

Let

w0 be the node at which J meets C(u,v)

w0' be the node at which J meets C(v,u)

w1 be the node at which J meets C(u1,v1)

w1' be the node at which J meets C(v1,u1).

There are four cases to consider, depending on the relative locations on C of these four nodes.

Case 1. One of w1 and w1' is on C(u,v) and the other is on C(v,u). Without loss of generality we can assume w0 = w1 and w0' = w1'. The situation appears as in Figure 5c.9a.

Image

Image

Figure 5c.9a. Orientation is clockwise around the geometric circle representing the graphical cycle, labeled C in the text. The animation shows where the K3,3 is; readers should construct comparable animations, from red nodes to black nodes, for subsequent figures in this proof.


But then G contains a subgraph homeomorphic to K3,3 (u, v, w0 are in one part; v, u, w0' are in the other).

Case 2. Both w1 and w1' are on either C(u,v) or C(v,u). Without loss of generality, assume the first situation. There are three possibilities.

Case 2a. vw0' and w0' lies on C(u1, v1), is in Figure 5c.9.b.

Image

Figure 5c.9.b. Orientation is clockwise around the geometric circle representing the graphical cycle, labeled C in the text.

Again G contains a subgraph homeomorphic to K3,3 (with u, u1, w0' in one part; v, v1, w1 in the other).

Case 2b. v1 w0' and w0' lies on C(v1,u1), as in Figure 5c.9.c.

Image

Figure 5c.9.c Orientation is clockwise around the geometric circle representing the graphical cycle, labeled C in the text.

Again there is a K3,3 homeomorphic (u, v1, w1 in one part: v, u1, w0' in the other).

Case 2c. v1 = W0' (as in Figure 5c.9.d). Now J must contain a node r from which there are disjoint paths in H to w1, w1', and v (since J separates u1 and v1).

Image

Figure 5c.9.d Orientation is clockwise around the geometric circle representing the graphical cycle, labeled C in the text.

Hence there is again a K3,3 (v1, w1, w1' in one part; r, u1, v in the other).

Case 3. w1 = v and w1' ≠ u. Without loss of generality assume w1' lies on C(u,v).

Case 3a. w0' is on C(v,v1), as in Figure 5c.9.e.

Image

Figure 5c.9.e Orientation is clockwise around the geometric circle representing the graphical cycle, labeled C in the text.

Still there is a K3,3 (u, u1, w0' in one part; v, v1, w1' in the other).

Case 3b. w0' is on C(v1,u), as in Figure 5c.9.f.

Image

Figure 5c.9.f Orientation is clockwise around the geometric circle representing the graphical cycle, labeled C in the text.

Again there is a K3,3 (u, r, v1 in one part; v, w0', w1' in the other). Even if w0' = v1, there is a K3,3 with u1 replacing v1 in the first part.

Case 4. w1 = v and w1' = u. here we can assume w0 = u1 and w0' = v1, or a situation covered in a previous case arises.

Let P0 be a shortest path in J from u to v1

and

let P1 be a shortest path in J from u1 to v1.

These paths must intersect.

Case 4a. They have at least two nodes r, s in common. The situation is illustrated in Figure 5c.9.g.

Image

Figure 5c.9.g Orientation is clockwise around the geometric circle representing the graphical cycle, labeled C in the text.

Again there is a K3,3 (u, v1, s in one part; v, u1, r in the other).

Case 4b. They have only one node r in common, as in Figure 5c.9.h.

Image

Figure 5c.9.h Orientation is clockwise around the geometric circle representing the graphical cycle, labeled C in the text.

Now u, v, u1, v1, and r are the nodes of a K5.

Since all possibilities have been exhausted, the Theorem is proved.