Unit 10: Planar graphs

Drawing without crossings

Circuit boards, metro maps and road junctions all work best when lines don't cross. Some graphs can be drawn flat with no crossings and some can't. A single formula from 1752, V − E + F = 2, tells them apart and even explains why there are only five perfectly regular solids.

1234567891011
In this unit
  1. The three utilities puzzle
  2. Planar graphs
  3. Faces
  4. Euler's formula
  5. How many edges can a planar graph have?
  6. K5 and K3,3 are not planar
  7. Kuratowski's theorem
  8. The five Platonic solids
  9. Planarity in the real world
  10. Practice set
  11. Summary and glossary

The three utilities puzzle

Three houses each need to be connected to three utilities: gas, water and electricity. Can you lay all nine pipes and cables so that none of them cross? (Assume everything is in a flat plane, with no tunnels or bridges, and pipes can't pass through houses.)

Three houses, three utilitiesEach of three houses joined to gas, water and power: nine lines with many crossings.H1H2H3GasWaterPower

The obvious drawing: many crossings

The best you can do: one crossingThe houses and utilities placed alternately around a hexagon. Six lines go round the hexagon, one across the middle, one around the outside. The ninth line, from H3 to gas, has to cross the line from H1 to water.H1GasH2WaterH3Power

A clever drawing: still one crossing

Houses (blue) and utilities (amber). Arranging them alternately around a hexagon gets eight of the nine lines in without crossings: six round the hexagon, one across the middle, one around the outside. But the ninth (pink, dashed) is blocked whichever way it goes.

People have tried this puzzle for over a century, and it's genuinely impossible. The graph here is the complete bipartite graph K3,3 (Unit 1). By the end of this unit you'll be able to prove that it can't be drawn without a crossing, in three lines of arithmetic.

Planar graphs

Definition

A graph is planar if it can be drawn in the plane with no edges crossing. Such a crossing-free drawing is called a plane drawing (or embedding).

The word "can" matters. Remember from Unit 1 that a graph is only its vertices and edges; the drawing is our choice. A graph drawn with crossings might still be planar if it can be redrawn without them:

K4 with a crossingFour vertices at the corners of a square, all six edges drawn straight; the diagonals cross.1234

A drawing with a crossing

K4 without crossingsThree vertices in a triangle with the fourth in the middle: no edges cross.1234

The same graph, no crossings

The complete graph K4 is planar. Both pictures have the same six edges joining all pairs of 1, 2, 3, 4. Moving vertex 4 into the middle removes the crossing.

Some families are always planar: every tree (Unit 3), every cycle, and every graph you get from a map (Unit 9). It's also a fact (Fáry's theorem, 1948) that if a graph can be drawn without crossings using curves, it can also be drawn without crossings using only straight lines.

Faces

A plane drawing cuts the paper into regions, like a map cuts land into countries. These regions are called faces. The unbounded region surrounding the whole drawing counts as a face too, the outer face.

Faces of a plane drawingA square with a diagonal and a triangular roof. Three shaded regions inside plus the region outside: four faces.ABCDE1234 (outside)

5 vertices, 7 edges, 4 faces

The cube, flattenedThe cube's 8 corners and 12 edges drawn as a square inside a square with corners joined.

The cube: 8 vertices, 12 edges, 6 faces

Counting faces. Left: three shaded faces plus the outside make 4. Right: imagine looking into a cube through its front face and flattening it. The small middle square is the back face, the four trapezoids are the sides, and the outside is the front face: 6 faces, just like a real cube.

Euler's formula

Count vertices (V), edges (E) and faces (F) for the two drawings above:

DrawingVEFV − E + F
House with diagonal5742
Cube81262
K44642
A tree with 10 vertices10912

It's always 2. Euler noticed this for solid shapes in 1752, and it holds for every plane drawing of a connected graph:

V − E + F = 2 Euler's formula, for any connected plane drawing

Why it's true. Start with a spanning tree of the graph (Unit 3). A tree has V − 1 edges and, since it has no cycles to enclose anything, just 1 face. So V − (V − 1) + 1 = 2. Now add the missing edges back one at a time. Each new edge joins two vertices that are already connected, so it closes a loop and splits one face into two: E goes up by 1 and F goes up by 1. The total V − E + F doesn't change. When all the edges are back, it's still 2.

Remarkably, the number of faces doesn't depend on how you draw the graph. Every plane drawing of a given connected planar graph has exactly F = 2 − V + E faces.

Try it. A connected planar graph has 10 vertices and 15 edges. How many faces does any plane drawing of it have? What if it had 3 components instead of being connected?

Show answer

Connected: F = 2 − 10 + 15 = 7. With 3 components, the formula becomes V − E + F = 1 + (number of components) = 4, so F = 4 − 10 + 15 = 9. (All the components share the one outer face.)

How many edges can a planar graph have?

Euler's formula has a powerful consequence: planar graphs can't have too many edges.

Take a simple planar graph with at least 3 vertices. Every face is surrounded by at least 3 edges (no loops or double edges means no faces with 1 or 2 sides). And every edge borders at most 2 faces, one on each side. Counting edge–face contacts both ways gives 3F ≤ 2E. Put that into Euler's formula:

E ≤ 3V − 6 For every simple planar graph with V ≥ 3. If there are no triangles, the stronger E ≤ 2V − 4 holds.

For triangle-free graphs, every face has at least 4 sides, so 4F ≤ 2E, giving the stronger bound.

Another consequence: every planar graph has a vertex of degree 5 or less. If every vertex had degree 6 or more, the handshake lemma (Unit 1) would give 2E ≥ 6V, so E ≥ 3V, breaking the bound. This little fact is the key step in proving that planar graphs can be coloured with 6 colours, then 5, on the way to the four colour theorem of Unit 9.

K5 and K3,3 are not planar

K5Five vertices, all ten edges.

K55 vertices, 10 edges

K3,3Three vertices joined to three others: nine edges.

K3,36 vertices, 9 edges

The Petersen graphAn outer pentagon, an inner five-pointed star, and spokes joining them: 10 vertices, 15 edges.

Petersen graph10 vertices, 15 edges

Three graphs that can't be drawn flat. However you move the vertices, some edges must cross.

The edge bounds give quick proofs:

K5 is not planar

V = 5 and E = 10. A planar graph with 5 vertices can have at most 3 × 5 − 6 = 9 edges. 10 is too many.

K3,3 is not planar (the utilities puzzle is impossible)

V = 6 and E = 9. Being bipartite, it has no triangles (a triangle would be an odd cycle; see Unit 9). So a plane drawing could have at most 2 × 6 − 4 = 8 edges. 9 is too many, so no arrangement of pipes avoids a crossing.

Note that 3V − 6 is only a test for non-planarity. A graph can satisfy it and still not be planar: K3,3 has 9 ≤ 3 × 6 − 6 = 12, and only the sharper triangle-free bound catches it.

Try it. Use the edge bounds to show the Petersen graph isn't planar. (Hint: its shortest cycle has length 5.)

Show answer

If every face has at least 5 sides, then 5F ≤ 2E, so F ≤ 2 × 15 ÷ 5 = 6. But Euler's formula would need F = 2 − 10 + 15 = 7 faces. 7 > 6, a contradiction, so the Petersen graph isn't planar.

Kuratowski's theorem

K5 and K3,3 turn out to be the only reasons a graph can fail to be planar. If you take K3,3 and put extra vertices in the middle of some edges (a subdivision), it still can't be drawn flat, because the long edges still behave like the original ones. Kazimierz Kuratowski proved in 1930 that this is the whole story:

Kuratowski's theorem

A graph is planar if and only if it does not contain a subdivision of K5 or of K3,3.

So these two small graphs are the fundamental obstacles. The Petersen graph, for example, contains a subdivision of K3,3 hidden inside it. Computers can test whether a graph with millions of vertices is planar, and draw it without crossings if it is, in time proportional to the size of the graph.

The five Platonic solids

A Platonic solid is a convex 3D shape whose faces are all the same regular polygon, with the same number of faces meeting at every corner. The ancient Greeks knew five. Euler's formula proves there can be no others.

Flatten the solid into a plane drawing as we did with the cube. Suppose each face has p sides and q edges meet at each corner. Counting edge ends: pF = 2E and qV = 2E. Substituting into V − E + F = 2 and dividing by 2E gives:

1/p + 1/q = 1/2 + 1/E > 1/2 Faces need p ≥ 3 sides and corners need q ≥ 3 edges

If both p and q were 4 or more, the left side would be at most 1/4 + 1/4 = 1/2, too small. So one of them must be 3, and the other can only be 3, 4 or 5 (since 1/3 + 1/6 is exactly 1/2). That leaves exactly five possibilities:

SolidFace shape (p)At each corner (q)VEF
Tetrahedrontriangle (3)3464
Cubesquare (4)38126
Octahedrontriangle (3)46128
Dodecahedronpentagon (5)3203012
Icosahedrontriangle (3)5123020

Check any row: V − E + F = 2. (The dodecahedron is the solid from Hamilton's Icosian game in Unit 6.) A purely graph-theoretic counting argument has settled a question of 3D geometry.

Planarity in the real world

Practice set

Mixed questions covering the whole unit. Try each one before opening the answer.

1. A connected plane drawing has 12 vertices and 6 faces. How many edges does it have?

Show answer

12 − E + 6 = 2, so E = 16.

2. Can a simple planar graph have 8 vertices and 20 edges?

Show answer

No. The maximum is 3 × 8 − 6 = 18 edges.

3. For which n is the complete graph Kn planar?

Show answer

n ≤ 4. K1 to K4 can be drawn flat (we drew K4). K5 can't, and every larger complete graph contains K5.

4. Is K2,10 planar?

Show answer

Yes. Put the two special vertices at the top and bottom and the ten others in a horizontal row between them. Each middle vertex is joined to both, and no lines cross. (It doesn't contain K3,3, which needs three vertices on each side.)

5. A soccer ball is stitched from pentagons and hexagons, with 3 patches meeting at every corner. Using Euler's formula, show that it must have exactly 12 pentagons.

Show answer

Let there be P pentagons and H hexagons, so F = P + H. Counting edges: 2E = 5P + 6H. Counting corners: 3V = 2E. Then 6(V − E + F) = 12 becomes 4E − 6E + 6P + 6H = 12, so 6P + 6H − (5P + 6H) = 12, giving P = 12. The number of hexagons can vary (a classic ball has 20), but there are always exactly 12 pentagons.

6. A planar graph has every vertex of degree at least 5. What's the smallest number of vertices it could have?

Show answer

Degrees ≥ 5 means 2E ≥ 5V; planarity means E ≤ 3V − 6. So 5V/2 ≤ 3V − 6, giving V ≥ 12. The icosahedron (12 vertices, each of degree 5) shows 12 is possible.

Summary and glossary

  1. A graph is planar if it can be drawn with no crossings. Trees, cycles, K4 and map graphs are planar.
  2. A plane drawing divides the plane into faces, including the outer face.
  3. Euler's formula: V − E + F = 2 for every connected plane drawing.
  4. Simple planar graphs have E ≤ 3V − 6 (or ≤ 2V − 4 without triangles), and always have a vertex of degree ≤ 5.
  5. K5 and K3,3 are not planar; by Kuratowski's theorem they are the only fundamental obstacles.
  6. Euler's formula proves there are exactly five Platonic solids.
Planar graph
A graph that can be drawn in the plane without crossings.
Plane drawing
A drawing of a graph with no crossings.
Face
A region of the plane bounded by edges of a plane drawing.
Outer face
The unbounded region surrounding the drawing.
Euler's formula
V − E + F = 2 for connected plane drawings.
Subdivision
A graph made by inserting new vertices in the middle of edges.
Kuratowski's theorem
Planar exactly when there is no subdivision of K5 or K3,3 inside.
Platonic solid
A convex solid with identical regular faces and identical corners.
Powered by Webloyt | Report abuse