Planar graphs and Euler's formula
Some networks can be drawn flat with no two links crossing and some cannot. When a flat drawing exists, what does it force on the numbers of points, links and regions, and how does that prove some networks can never be drawn flat?
Where you are 10 in Introductory graph theory
Why this exists
A circuit board with copper on one layer, a subway map with no bridges, a puzzle about pipes: each asks whether a network can be drawn flat with no two links crossing. Trying drawings settles the question only when one works. Euler’s formula turns it into arithmetic: a flat drawing of a connected network always has vertices minus edges plus regions equal to 2. Since every region needs at least three edges around it, the formula caps the number of edges, and that cap proves that K_5 and the three-utilities graph can never be drawn flat.
Definition
This lesson takes two days. Day 1 is plane drawings, faces and Euler’s formula (Results 1 and 2, Examples 1 to 4). Day 2 is the edge bounds, the two smallest graphs that cannot be drawn flat, and Kuratowski’s theorem (Results 3 to 7, Examples 5 to 7).
The notation is that of Degree, the handshake lemma and complete graphs and Walks, paths, cycles and connected graphs: G = (V, E) is a finite simple graph, and paths, cycles, connected graphs and components are as defined there. Trees and forests are as in Trees, and G - xy is G with the edge xy erased.
- A plane drawing of G puts each vertex at its own point and draws each edge xy as a curve from x to y that does not cross itself and passes through no other vertex, so that two edges meet only at a shared endpoint. G is planar if it has a plane drawing; a plane graph is a graph together with one plane drawing of it.
- Erasing the drawing from the plane leaves separate regions, the faces. Exactly one face is unbounded, the outer face.
- Here v = \lvert V \rvert, e = \lvert E \rvert, f is the number of faces and c the number of components. A single edge is always named by its endpoints, as xy.
- (Day 2) Each edge has two sides, and each side borders exactly one face. The degree \deg(F) of a face F is the number of edge sides bordering it, so an edge with F on both sides counts twice.
- (Day 2) The complete bipartite graph K_{m,n} has a group of m vertices and a group of n, every vertex of one group joined to every vertex of the other, and no edge inside a group (more in Bipartite graphs).
- (Day 2) Subdividing the edge xy replaces it by a new vertex w and edges xw, wy. A subdivision of H is a graph made from H by subdividing edges any number of times.
Erasing vertices or edges from a plane drawing leaves a plane drawing, so every subgraph of a planar graph is planar. Two facts about drawings are used without proof; they rest on the Jordan curve theorem (a closed curve that does not cross itself splits the plane into an inside and an outside), which belongs to topology.
- (P1) If an edge lies on a cycle, the faces on its two sides are different, and erasing the edge merges them into one, leaving every other face as it was. If an edge lies on no cycle, the same face is on both its sides, and erasing it leaves the number of faces as it was.
- (P2) In a connected plane graph with an edge, walking once around a face F runs along each edge side bordering F once. Its vertices form a closed walk of length \deg(F), the boundary walk of F.
Intuition
Eyota designs circuit boards with copper on one layer. Parts are vertices and traces are edges; traces that crossed would short, so a working layout is a plane drawing, and the bare board falls into regions, the faces.
Why should v - e + f never change? Build a connected layout from one part. A new part with one trace to it raises v and e by 1 and cuts no region. A trace between two parts already joined closes a loop and cuts one region in two, raising e and f by 1. Neither move changes v - e + f, and one part alone has 1 - 0 + 1 = 2.
Results
1. Euler’s formula. Every connected plane graph has
So every plane drawing of a connected planar graph has the same number of faces, f = 2 - v + e.
2. Several components. A plane graph with c components has v - e + f = 1 + c.
3. Counting edge sides (Day 2). In every plane graph
4. Edge bounds (Day 2). Let G be a simple connected planar graph with v \ge 3. Then e \le 3v - 6, and if G has no triangle (no cycle of length 3), e \le 2v - 4. The first bound holds for a disconnected G with v \ge 3 as well.
5. Two graphs that cannot be drawn flat (Day 2). K_5 and K_{3,3} are not planar.
6. A vertex of small degree (Day 2). Every simple planar graph has a vertex of degree at most 5.
7. Kuratowski’s theorem (Day 2). A graph is planar exactly when no subgraph of it is a subdivision of K_5 or of K_{3,3}. Kazimierz Kuratowski proved it in 1930; it is stated here without proof.
Why it is true
Results 1 and 2. Proof. Result 1 is the case c = 1 of Result 2, so we prove Result 2 by induction on e (How induction works: base case, hypothesis and step): every plane graph with e edges has v - e + f = 1 + c.
No cycle. If G has no cycle (as when e = 0), it is a forest, so e = v - c (Trees, Result 4). Its drawing has one face: join two points off the drawing by a curve avoiding the vertices; by (P1) each edge has one face on both sides, so crossing an edge never changes face. So v - e + f = v - (v - c) + 1 = 1 + c. This settles e = 0.
A cycle. Let e \ge 1, assume the claim for e - 1 edges, and let xy be an edge on a cycle of G. A walk that used xy can go around the rest of the cycle instead, so G - xy has the same components. By (P1) the two faces beside xy merge, so G - xy has v vertices, e - 1 edges, f - 1 faces and c components. By the induction hypothesis v - (e - 1) + (f - 1) = 1 + c, which is v - e + f = 1 + c. \square
Result 3. Proof. Count edge sides. By edge there are two each, 2e in all; by face there are \sum_F \deg(F), since each side borders exactly one face. \square It is the two-way count of the handshake lemma, with faces in place of vertices.
Result 4. Proof. Draw G. It is connected with v \ge 3, so it has at least two edges and each face has a boundary walk, closed of length \deg(F) by (P2). Length 1 would be a loop. Length 2 is (x, y, x): then F borders both sides of xy and nothing else, the walk turns back at x and at y, so no other edge meets x or y, and G would be the single edge xy. So every \deg(F) \ge 3, Result 3 gives 3f \le 2e, and with f = 2 - v + e from Result 1,
With no triangle, length 3 is ruled out too: a closed walk (x, y, z, x) has x, y, z different (each step is an edge, and there are no loops), so it is a triangle. Then 4f \le 2e, and 4(2 - v + e) \le 2e gives e \le 2v - 4.
If G has c \ge 2 components, with v_i vertices and e_i edges in the ith, then e_i \le 3v_i - 3: by the bound when v_i \ge 3, and since e_i \le 1 when v_i \le 2. Adding, e \le 3v - 3c \le 3v - 6. \square
Result 5. Proof. By Proof by contradiction. K_5 is simple and connected with v = 5 and e = \binom{5}{2} = 10; if it were planar, Result 4 would give 10 \le 3 \cdot 5 - 6 = 9. K_{3,3} has v = 6 and e = 9, and no triangle: of any three vertices two share a group and are not joined. If it were planar, 9 \le 2 \cdot 6 - 4 = 8. Both are false. \square
K_{3,3} is an old puzzle in disguise. Three cabins each want a line from a well, a generator and a propane tank, laid on the ground with no two lines crossing. Cabins and supplies are the two groups and the nine lines the edges, so it cannot be done.
Result 6. Proof. Let G be simple and planar. If a component has at most 2 vertices, a vertex in it has degree at most 1. Otherwise take a component H, with v_H \ge 3 vertices and e_H edges. It is simple, connected and planar, so by the handshake lemma and Result 4,
So not every vertex of H has degree 6 or more; one has degree at most 5, in G as in H. \square
Result 7. One direction is short. If a subgraph S of a planar G were a subdivision of K_5 or K_{3,3}, then S would be planar; in its drawing, erase the dot of each subdividing vertex and let its two curves run together as one. That is a plane drawing of K_5 or K_{3,3}, which Result 5 forbids. The other direction, that every nonplanar graph contains such a subgraph, is the deep part.
Worked examples
Counting the faces of a board
Find v, e and f for Eyota’s board in Figure 1 and check Euler’s formula. Which faces lie on the two sides of FG, and of BC?
SolutionThe parts are A to G, so v = 7. The traces are the square’s four sides, AE, EC, BF, CF and FG, so e = 9. The path A, E, C cuts the square into F_1 (bordered by AB, BC, CE, EA) and F_2 (by AE, EC, CD, DA); the triangle B, F, C encloses F_3; the rest is the outer face F_4. So f = 4, and since the board is connected,
as Result 1 requires. FG lies on no cycle, since \deg(G) = 1 and a cycle leaves each of its vertices by an edge other than the one it arrived on; so by (P1) F_4 is on both sides of FG. BC lies on the cycle (B, F, C, B), so its sides are in different faces: F_1 on one side and F_3 on the other.
Faces without a drawing
Eyota plans a connected board with 8 parts, each carrying exactly 4 traces, and no crossings. How many regions of bare board will it have? Show that such a board exists.
SolutionBy the handshake lemma 2e = 8 \cdot 4 = 32, so e = 16, and Result 1 gives
for every such layout, before any is drawn. One exists: a square of parts with a smaller square inside, turned by 45^\circ, each inner part joined to the two outer corners nearest it. Every part has two neighbors on its own square and two on the other. The faces are the inner square, the 8 triangles between the squares and the outer face: 10.
A board in three pieces
Another board carries three separate circuits, with 15 parts and 16 traces in all and no crossings. How many regions of bare board does it have?
SolutionWith c = 3 components Result 1 does not apply, but Result 2 does:
For instance: K_4 drawn as a triangle with a part inside joined to the corners (4 parts, 6 traces, 3 bounded faces), a ring of 5 parts (5 traces, 1 bounded face) and a tree of 6 parts (5 traces), placed apart: 3 + 1 bounded faces and one outer face shared by all three.
A solid flattened
A hexagonal pyramid has a hexagon for its base and six triangles meeting at its apex. Draw its vertices and edges flat with no crossings, and check Euler’s formula. Where did the base go?
SolutionLook down on the apex and press the solid flat: the apex lands at the center of the hexagon, and its six slanting edges become spokes (Figure 3).
No two edges cross, so this is a plane drawing of a connected graph with v = 7 and e = 6 + 6 = 12. The six triangles are the bounded faces, and the base is now the outer face: f = 7. So
Every convex polyhedron flattens this way: hold one face close to the eye and look through it, and the rest of the solid appears inside that face with no edges crossing; that face becomes the outer face. So Euler’s formula gives V - E + F = 2 for every convex polyhedron, the rule that Polyhedra checks on examples and The five regular solids uses to find the five regular solids.
Too many traces
Eyota wants a board with 8 parts and at most one trace between any two parts. (a) Can it carry 19 traces on one layer? (b) If no three parts may be joined in pairs, what is the most it can carry, and is that reached?
Solution(a) No. The graph is simple with v = 8 \ge 3, so if it were planar, Result 4 would give e \le 3 \cdot 8 - 6 = 18 < 19, connected or not.
(b) Now there is no triangle. If the graph is connected, e \le 2 \cdot 8 - 4 = 12. If it has c \ge 2 components, each has e_i \le 2v_i - 2 (by that bound when v_i \ge 3, and since e_i \le v_i - 1 when v_i \le 2), so e \le 2 \cdot 8 - 2c \le 12. A cube’s edges reach 12: a square inside a square with matching corners joined, every degree 3, so \displaystyle e = \frac{8 \cdot 3}{2} = 12. Color the outer corners black and white in turn and each inner corner opposite to its partner; every edge joins two colors, so no three corners are joined in pairs. The most is 12.
The four-dimensional cube
The graph Q_4 has the 16 strings of four bits (each 0 or 1) as vertices, two joined when they differ in exactly one place. Show that Q_4 is not planar.
SolutionEach string has 4 neighbors, one per place, so \displaystyle e = \frac{16 \cdot 4}{2} = 32. The graph is simple, and connected: change the places where two strings differ one at a time.
It has no triangle. Along an edge the number of 1s changes by exactly 1, so its parity flips. A triangle is a closed walk of 3 steps, and after an odd number of flips the parity differs from the start (Proving statements about even and odd numbers), yet the walk ends where it began.
So if Q_4 were planar, Result 4 would give 32 \le 2 \cdot 16 - 4 = 28, which is false. The bound 3v - 6 = 42 would have settled nothing.
Fewer than twelve vertices
Prove that every simple planar graph with at most 11 vertices has a vertex of degree at most 4.
SolutionProof. Suppose G is simple and planar with v \le 11 and every degree at least 5. Take a component H with v_H vertices and e_H edges. A vertex of H has its 5 or more neighbors in H, so v_H \ge 6, and H is simple, connected and planar. By the handshake lemma 2e_H \ge 5v_H, and by Result 4 e_H \le 3v_H - 6. Together,
But v_H \le v \le 11, a contradiction. \square
The 11 cannot become 12: the icosahedron’s 12 corners each meet 5 edges (The five regular solids), and flattened as in Example 4 it is a planar graph with every degree 5.
Boundaries
- Simple graphs, at least three vertices. The edge bounds fail for multigraphs: two vertices joined by any number of edges, drawn as nested arcs, are planar. For v = 2, K_2 has e = 1 > 3 \cdot 2 - 6 = 0.
- Connected, or count components. v - e + f = 2 is for connected plane graphs; with c components it is 1 + c (Example 3).
- One-way tests. A planar graph meets e \le 3v - 6 and e \le 2v - 4, but a graph meeting them need not be planar: K_{3,3} meets the first, the graph of Exercise 17 both. Only Kuratowski’s theorem settles every graph.
- The plane. On the surface of a donut (a torus) K_5 and K_{3,3} can be drawn with no crossings, and a torus drawing whose faces are all disks has v - e + f = 0 (stated without proof).
Where this goes next
Result 6 is the first step in Graph coloring: a vertex of degree at most 5 can be set aside and colored last, which shows that six colors suffice for every planar graph, and that lesson takes the story to four. Graphs in two groups, like K_{m,n}, are Bipartite graphs. Planarity survives relabeling the vertices, so it helps tell graphs apart in Graph isomorphism: when two drawings are the same graph.
Exercises
Faces and Euler’s formula (Day 1)
Exercises 1 to 3 and 10 use the plane graph H of Figure 4, with edges 12, 23, 34, 41, 13, 25, 35, 56, 67, 78, 86.
- Find v, e and f for H, name each face by the edges around it, and check Euler’s formula.
- Which edges of H have the same face on both sides? Give the reason.
- Erase the edge 13 from H and count the faces. Then erase 56 from H instead, count the faces and components, and check Result 2.
- A connected plane graph has 20 vertices and 31 edges. How many faces does it have?
- A connected plane graph has every vertex of degree 3 and has 9 faces. Find v and e, and describe a graph that fits.
- A plane graph has 4 components, 30 edges and 11 faces. How many vertices does it have?
- A heptagonal pyramid has a seven-sided base and seven triangles meeting at its apex. Draw its vertices and edges flat twice, once with the base as the outer face and once with a triangle as the outer face, and check Euler’s formula for each.
- A forest has 10 vertices and 3 components. Find e and f for any plane drawing of it, and check Result 2.
- The wheel W_n, for n \ge 3, is the cycle C_n with one more vertex, the hub, joined to all n vertices of the cycle. Find v, e and f for the drawing with the hub in the middle.
Edge bounds and nonplanar graphs (Day 2)
- Find the degree of every face of H, and check Result 3.
- For which n \ge 1 is K_n planar? Prove it.
- A simple planar graph has 10 vertices. What is the largest number of edges it can have? What if it also has no triangle? Show that both numbers are reached.
- Is there a convex polyhedron with 10 vertices and 25 edges?
- Show that K_{2,n} is planar for every n \ge 1, and that K_{3,n} is not planar for n \ge 3.
- A simple connected plane graph has 7 vertices and every face has degree 3. Find e and f.
- A simple connected planar graph has every vertex of degree 3 and no triangle. Show that v \ge 8, and give such a graph with v = 8.
- Subdivide every edge of K_5 once. Find v and e, show the new graph has no triangle, check that it meets both bounds of Result 4, and explain why it is still not planar.
Reasoning
- Prove that a simple connected plane graph with v \ge 3 has at most 2v - 4 faces.
- Prove that if a simple connected plane graph with v \ge 3 has e = 3v - 6, then every face has degree 3.
- Let G be a simple graph with 11 vertices. Prove that G or its complement \overline{G} is not planar.
- Refute with a counterexample: “a graph with no subgraph equal to K_5 or to K_{3,3} is planar.”
- Let xy lie on no cycle of a plane graph G. Show that G - xy has one more component than G and the same number of faces, so that v - e + f - c is the same for both.
Answers
- v = 8, e = 11, f = 5: the triangles bordered by 12, 23, 13; by 13, 34, 41; by 23, 35, 25; by 67, 78, 86; and the outer face. 8 - 11 + 5 = 2.
- Only 56. Every other edge lies on a triangle, so (P1) puts different faces on its sides. Erasing 56 leaves no edge between \{1, \ldots, 5\} and \{6, 7, 8\}, so no cycle uses 56, and the outer face is on both its sides.
- Without 13 its two triangles merge: f = 4, and 8 - 10 + 4 = 2. Without 56 no face changes: f = 5, c = 2, and 8 - 10 + 5 = 3 = 1 + 2.
- f = 2 - 20 + 31 = 13.
- v = 14, e = 21, from 2e = 3v and \displaystyle v - \frac{3v}{2} + 9 = 2. Two 7-cycles, one inside the other, matching vertices joined: 7 four-sided faces, the inner face and the outer face.
- v = 1 + c + e - f = 1 + 4 + 30 - 11 = 24.
- Both have v = 8, e = 14, f = 8, and 8 - 14 + 8 = 2. Base outside: the apex in the middle of the heptagon. A triangle outside: the apex and two base corners drawn large, the other five corners inside, the base now a bounded heptagon.
- e = v - c = 7 (Trees) and f = 1, and 10 - 7 + 1 = 4 = 1 + 3.
- v = n + 1, e = 2n (rim and spokes), f = n + 1 (n triangles and the outer face), and (n + 1) - 2n + (n + 1) = 2.
- The four triangles have degree 3; the outer face has degree 10, with boundary walk (1, 2, 5, 6, 7, 8, 6, 5, 3, 4, 1) using 56 twice. 4 \cdot 3 + 10 = 22 = 2 \cdot 11.
- Exactly for n \le 4. K_4 is a triangle with a fourth vertex inside joined to the corners, and K_1 to K_3 are its subgraphs. For n \ge 5, K_n contains K_5, so it is not planar by Result 5.
- 24 = 3 \cdot 10 - 6, and 16 = 2 \cdot 10 - 4 (if disconnected, by components as in Example 5). Start from a triangle and 7 times put a vertex inside a triangular face, joined to its corners: 10 vertices and 3 + 21 = 24 edges. K_{2,8} has 10 vertices, 16 edges, no triangle, and is planar (Exercise 14).
- No: its flattened graph is simple, connected and planar, with 25 > 3 \cdot 10 - 6 = 24 edges.
- Put the two vertices of one group above and below a horizontal line holding the other n. Straight edges from the top vertex stay above the line, those from the bottom below: a plane drawing. For n \ge 3, K_{3,n} contains K_{3,3}, so it is not planar.
- e = 15, f = 10, from 2e = 3f (Result 3) and f = 2 - 7 + e, so 2e = 3(e - 5).
- \displaystyle e = \frac{3v}{2}, and Result 4 gives \displaystyle \frac{3v}{2} \le 2v - 4, so v \ge 8. The cube of Example 5 has v = 8.
- v = 5 + 10 = 15 and e = 2 \cdot 10 = 20. Every edge joins an old vertex to a new one, so as for K_{3,3} there is no triangle. 20 \le 3 \cdot 15 - 6 = 39 and 20 \le 2 \cdot 15 - 4 = 26. It is a subdivision of K_5, so it is not planar (the short direction of Result 7).
- By Results 1 and 4, f = 2 - v + e \le 2 - v + 3v - 6 = 2v - 4.
- By Result 1, f = 2v - 4, so 3f = 6v - 12 = 2e. Every face has degree at least 3 (proof of Result 4) and the degrees add to 2e = 3f, so a face of degree 4 or more is impossible.
- G and \overline{G} have \binom{11}{2} = 55 edges together (Degree, the handshake lemma and complete graphs). If both were planar, Result 4 (without connectedness) would give 55 \le 2(3 \cdot 11 - 6) = 54.
- K_{3,3} with one edge xy subdivided by w: 7 vertices, 10 edges. Every degree is at most 3, so there is no K_5. A K_{3,3} would need six vertices of degree 3, the original six, and nine edges among them; only 8 remain. Yet it is a subdivision of K_{3,3}, so not planar.
- If a walk in G - xy joined x to y, so would a path (Walks, paths, cycles and connected graphs, Result 1), and with xy it would make a cycle. So x and y fall in different components, and every vertex joined to them in G stays joined to one of them (cut its walk at the first use of xy). So c goes up by 1, e down by 1, and by (P1) f is unchanged.