5.5: Planar Graphs

Let's return to the problem of providing lines for water, electricity, and natural gas to three homes which we discussed in the introduction to this chapter. How can we model this problem using a graph? The best way is to have a vertex for each utility and a vertex for each of the three homes. Then what we're asking is if we can draw the graph that has an edge from each utility to each home so that none of the edges cross. This graph is shown in Figure 5.29. You should recognize it as the complete bipartite graph \(K_{3,3}\) we introduced earlier in the chapter.

Figure 5.29. A graph of connecting homes to utilities

While this example of utility lines might seem a bit contrived, since there's really no good reason that the providers can't bury their lines at different depths, the question of whether a graph can be drawn in the plane such that edges intersect only at vertices is a long-studied question in mathematics that does have useful applications. One area where it arises is in the design of microchips and circuit boards. In those contexts, the material is so thin that the option of placing connections at different depths either does not exist or is severely restricted. There is much deep mathematics that underlies this area, and this section is intended to introduce a few of the key concepts.

By a drawing of a graph, we mean a way of associating its vertices with points in the Cartesian plane \(\mathbb{R}^2\) and its edges with simple polygonal arcs whose endpoints are the points associated to the vertices that are the endpoints of the edge. You can think of a polygonal arc as just a finite sequence of line segments such that the endpoint of one line segment is the starting point of the next line segment, and a simple polygonal arc is one that does not cross itself. (Our choice of polygonal arcs rather than arbitrary curves actually doesn't cause an impediment, since by taking very, very, very short line segments we can approximate any curve.) A planar drawing of a graph is one in which the polygonal arcs corresponding to two edges intersect only at a point corresponding to a vertex to which they are both incident. A graph is planar if it has a planar drawing. A face of a planar drawing of a graph is a region bounded by edges and vertices and not containing any other vertices or edges.

Figure 5.30 shows a planar drawing of a graph with 6 vertices and 9 edges. Notice how one of the edges is drawn as a true polygonal arc rather than a straight line segment. This drawing determines 5 regions, since we also count the unbounded region that surrounds the drawing.

Figure 5.30. A planar drawing of a graph

Figure 5.31 shows a planar drawing of the complete graph \(K_4\). There are 4 vertices, 6 edges, and 4 faces in the drawing.

Figure 5.31. A planar drawing of \(K_4\)

What happens if we compute the number of vertices minus the number of edges plus the number of faces for these drawings? We have

\(6-9+5=2\)

\(4-6+4=2\)

While it might seem like a coincidence that this computation results in 2 for these planar drawings, there's a more general principle at work here, and in fact it holds for any planar drawing of any planar graph.

In fact, the number 2 here actually results from a fundamental property of the plane, and there are a corresponding theorems for other surfaces. However, we only need the result as stated above.

Theorem 5.32. Euler's Formula

Let \(G\) be a connected planar graph with \(n\) vertices and \(m\) edges. Every planar drawing of \(G\) has \(f\) faces, where \(f\) satisfies

\(n-m+f=2\)

Proof

Our proof is by induction on the number \(m\) of edges. If \(m=0\), then since \(G\) is connected, our graph has a single vertex, and so there is one face. Thus \(n−m+f=1−0+1=2\) as needed. Now suppose that we have proven Euler's formula for all graphs with less than m edges and let \(G\) have \(m\) edges. Pick an edge \(e\) of \(G\). What happens if we form a new graph \(G′\) by deleting e from \(G\)? If \(G′\) is connected, our inductive hypothesis applies. Say that \(G′\) has \(n′\) vertices, \(m′\) edges, and \(f′\) faces. Then by induction, these numbers satisfy

\(n' - m' + f' = 2\).

Since we only deleted one edge, \(n′=n\) and \(m′=m−1\). What did the removal of \(e\) do to the number of faces? In \(G′\) there's a new face that was formerly two faces divided by \(e\) in \(G\). Thus, \(f′=f−1\). Substituting these into \(n′−m′+f′=2\), we have

\(n-(m-1) + (f-1) = 2 \Longleftrightarrow n-m+f = 2\).

Thus, if \(G′\) is connected, we are done. If \(G′\) is disconnected, however, we cannot apply the inductive assumption to \(G′\) directly. Fortunately, since we removed only one edge, \(G′\) has two components, which we can view as two connected graphs \(G_1′\) and \(G_2′\). Each of these has fewer than \(m\) edges, so we may apply the inductive hypothesis to them. For \(i=1,2\), let \(n_i′\) be the number of vertices of \(G_i′, m_i′\) the number of edges of \(G_i′, and f_i′\) the number of faces of \(G_i′\). Then by induction we have

\(n_1' - m_1' +f_1' = 2\) and \(n_2' - m_2' + f_2' = 2\).

Adding these together, we have

\((n_1' + n_2') - (m_1' + m_2') + (f_1' + f_2') = 4\).

But now \(n=n_1' + n_2'\) and \(m_1' + m_2' = m-1\), so the equality becomes

\(n - (m-1) + (f_1' + f_2') = 4 \Longleftrightarrow n-m + (f_1' + f_2') = 3\).

The only thing we have yet to figure out is how \(f_1′+f_2′\) relates to \(f\), and we have to hope that it will allow us to knock the 3 down to a 2. Every face of \(G_1′\) and \(G_2′\) is a face of \(G\), since the fact that removing \(e\) disconnects \(G\) means that \(e\) must be part of the boundary of the unbounded face. Further, the unbounded face is counted twice in the sum \(f_1′+f_2′\), so \(f=f_1′+f_2′−1\). This gives exactly what we need to complete the proof.

Taken by itself, Euler's formula doesn't seem that useful, since it requires counting the number of faces in a planar embedding. However, we can use this formula to get a quick way to determine that a graph is not planar. Consider a drawing without edge crossings of a graph on \(n\) vertices and m edges, with \(n \geq 3\). We consider pairs \((e,F)\) where \(e\) is an edge of \(G\) and \(F\) is a face that has \(e\) as part of its boundary. How many such pairs are there? Let's call the number of pairs \(p\). Each edge can bound either one or two faces, so we have that \(p \leq 2m\). We can also bound \(p\) by counting the number of pairs in which a face \(F\) appears. Each face is bounded by at least 3 edges, so it appears in at least 3 pairs, and so \(p \geq 3f\). Thus \(3f \leq 2m\) or \(f \leq 2m/3\). Now, utilizing Euler's formula, we have

\(m=n+f - 2 \leq n + \frac{2m}{3} - 2 \Longleftrightarrow \frac{m}{3} \leq n-2\).

Thus, we've proven the following theorem.

Theorem 5.33

A planar graph on \(n\) vertices has at most \(3n−6\) edges when \(n \geq 3\).

The contrapositive of this theorem, namely that an \(n\)-vertex graph with more than \(3n−6\) edges is not planar, is usually the most useful formulation of this result. For instance, we've seen (Figure 5.31) that \(K_4\) is planar. What about \(K_5\)? It has 5 vertices and \(C(5,2)=10>9=3 \cdot 5−6\) edges, so it is not planar, and thus for \(n \geq 5\), \(K_n\) is not planar, since it contains \(K_5\). It's important to note that Theorem 5.33 is not the be-all, end-all of determining if a graph is planar. To see this, let's return to the subject of drawing \(K_{3,3}\) in the plane. This graph has 6 vertices and 9 edges, so it passes the test of Theorem 5.33. However, if you spend a couple minutes trying to find a way to draw \(K_{3,3}\) in the plane without any crossing edges, you'll pretty quickly begin to believe that it can't be done—and you'd be right!

To see why \(K_{3,3}\) is not planar, we'll have to return to Euler's formula, and we again work with edge-face pairs. For \(K_{3,3}\), we see that every edge would have to be part of the boundary of two faces, and faces are bounded by cycles. Also, since the graph is bipartite, there are no odd cycles. Thus, counting edge-face pairs from the edge perspective, we see that there are \(2m=18\) pairs. If we let \(f_k\) be the number of faces bounded by a cycle of length \(k\), then \(f=f_4+f_6\). Thus, counting edge-face pairs from the face perspective, there are \(4f_4+6f_6\) pairs. From Euler's formula, we see that the number of faces \(f\) must be 5, so then \(4f_4+6f_6 \geq 20\). But from our count of edge-face pairs, we have \(2m=4f_4+6f_6\), giving \(18 \geq 20\), which is clearly absurd. Thus, \(K_{3,3}\) is not planar.

At this point, you're probably asking yourself “So what?” We've invested a fair amount of effort to establish that \(K_5\) and \(K_{3,3}\) are nonplanar. Clearly any graph that contains them is also nonplanar, but there are a lot of graphs, so you might think that we could be at this forever. Fortunately, we won't be, since at its core, planarity really comes down to just these two graphs, as we shall soon see.

If \(G=(V,E)\) is a graph and \(uv \in E\), then we may form a new graph \(G′\) called an elementary subdivision of \(G\) by adding a new vertex \(v′\) and replacing the edge \(uv\) by edges \(uv′\) and \(v′v\). In other words, \(G′\) has vertex set \(V′=V \cup \{v′\}\) and edge set \(E′=(E−\{uv\}) \cup \{uv′,v′v\}\). Two graphs \(G_1\) and \(G_2\) are homeomorphic if they can be obtained from the same graph by a (potentially trivial) sequence of elementary subdivisions.

The purpose of discussing homeomorphic graphs is that two homeomorphic graphs have the same properties when it comes to being drawn in the plane. To see this, think about what happens to \(K_5\) if we form an elementary subdivision of it via any one of its edges. Clearly it remains nonplanar. In fact, if you take any nonplanar graph and form the elementary subdivision using any one of its edges, the resulting graph is nonplanar. The following very deep theorem was proved by the Polish mathematician Kazimierz Kuratowski in 1930. Its proof is beyond the scope of this text.

Theorem 5.34. Kuratowski's Theorem

A graph is planar if and only if it does not contain a subgraph homeomorphic to either \(K_5\) or \(K_{3,3}\).

Kuratowski's Theorem gives a useful way for checking if a graph is planar. Although it's not always easy to find a subgraph homeomorphic to \(K_5\) or \(K_{3,3}\) by hand, there are efficient algorithms for planarity testing that make use of this characterization. To see this theorem at work, let's consider the Petersen graph shown in Figure 5.17. The Petersen graph has 10 vertices and 15 edges, so it passes the test of Theorem 5.33, and our argument using Euler's formula to prove that \(K_{3,3}\) is nonplanar was complex enough, we probably don't want to try it for the Petersen graph. To use Kuratowski's Theorem here, we need to decide if we would rather find a subgraph homeomorphic to \(K_5\) or to \(K_{3,3}\). Although the Petersen graph looks very similar to \(K_5\), it's actually simultaneously too similar and too different for us to be able to find a subgraph homeomorphic to \(K_5\), since each vertex has degree 3. Thus, we set out to find a subgraph of the Petersen graph homeomorphic to \(K_{3,3}\). To do so, note that \(K_{3,3}\) contains a cycle of length 6 and three edges that are in place between vertices opposite each other on the cycle. We identify a six-cycle in the Petersen graph and draw it as a hexagon and place the remaining four vertices inside the cycle. Such a drawing is shown in Figure 5.35. The subgraph homeomorphic to \(K_{3,3}\) is found by deleting the black vertex, as then the white vertices have degree two, and we can replace each of them and their two incident edges (shown in bold) by a single edge.

Figure 5.35. A more illustrative drawing of the Petersen graph

We close this section with a problem that brings the current section together with the topic of graph coloring. In 1852 Francis Guthrie, an Englishman who was at the time studying to be lawyer but subsequently became a professor of mathematics in South Africa, was trying to color a map of the counties of England so that any two counties that shared a boundary segment (meaning they touched in more than a single point) were colored with different colors. He noticed that he only needed four colors to do this, and was unable to draw any sort of map that would require five colors. (He was able to find a map that required four colors, an example of which is shown in Figure 5.36.)

Figure 5.36. A map that requires four colors

Could it possibly be true that every map could be colored with only four colors? He asked his brother Frederick Guthrie, who was a mathematics student at University College, London, about the problem, and Frederick eventually communicated the problem to Augustus de Morgan (of de Morgan's laws fame), one of his teachers. It was in this way that one of the most famous (or infamous) problems, known for a century as the Four Color Problem and now the Four Color Theorem, in graph theory was born. De Morgan was very interested in the Four Color Problem, and communicated it to Sir William Rowan Hamilton, a prominent Irish mathematician and the one for whom hamiltonian cycles are named, but Hamilton did not find the problem interesting. Hamilton is one of the few people who considered the Four Color Problem but did not become captivated by it.

We'll continue our discussion of the history of the Four Color Theorem in a moment, but first, we must consider how we can turn the problem of coloring a map into a graph theory question. Well, it seems natural that each region should be assigned a corresponding vertex. We want to force regions that share a boundary to have different colors, so this suggests that we should place an edge between two vertices if and only if their corresponding regions have a common boundary. (As an example, the map in Figure 5.36 corresponds to the graph \(K_4\).) It is not difficult to see that this produces a planar graph, since we may draw the edges through the common boundary segment. Furthermore, with a little bit of thought, you should see that given a planar drawing of a graph, you can create a map in which each vertex leads to a region and edges lead to common boundary segments. Thus, the Four Color Problem could be stated as “Does every planar graph have chromatic number at most four?”

Interest in the Four Color Problem languished until 1877, when the British mathematician Arthur Cayley wrote a letter to the Royal Society asking if the problem had been resolved. This brought the problem to the attention of many more people, and the first “proof” of the Four Color Theorem, due to Alfred Bray Kempe, was completed in 1878 and published a year later. It took 11 years before Percy John Heawood found a flaw in the proof but was able to salvage enough of it to show that every planar graph has chromatic number at most five. In 1880, Peter Guthrie Tait, a British physicist best known for his book Treatise on Natural Philosophy with Sir William Thomson (Lord Kelvin), made an announcement that suggested he had a proof of the Four Color Theorem utilizing hamiltonian cycles in certain planar graphs. However, consistent with the way Tait approached some conjectures in the mathematical theory of knots, it appears that he subsequently realized around 1883 that he could not prove that the hamiltonian cycles he was using actually existed and so Tait likely only believed he had a proof of the Four Color Theorem for a short time, if at all. However, it would take until 1946 to find a counterexample to the conjecture Tait had used in his attempt to prove the Four Color Theorem.

In the first half of the twentieth century, some incremental progress toward resolving the Four Color Problem was made, but few prominent mathematicians took a serious interest in it. The final push to prove the Four Color Theorem came with about at the same time that the first electronic computers were coming into widespread use in industry and research. In 1976, two mathematicians at the University of Illinois announced their computer-assisted proof of the Four Color Theorem. The proof by Kenneth Appel and Wolfgang Haken led the University of Illinois to add the phrase “FOUR COLORS SUFFICE” to its postage meter's imprint.

Theorem 5.37. Four Color Theorem

Every planar graph has chromatic number at most four.

Appel and Haken's proof of the Four Color Theorem was at a minimum unsatisfactory for many mathematicians, and to some it simply wasn't a proof. These mathematicians felt that the using a computer to check various cases was simply too uncertain; how could you be certain that the code that checked the 1,482 “unavoidable configurations” didn't contain any logic errors? In fact, there were several mistakes found in the cases analyzed, but none were found to be fatal flaws. In 1989, Appel and Haken published a 741-page tome entitled Every Planar Map is Four Colorable which provided corrections to all known flaws in their original argument. This still didn't satisfy many, and in the early 1990's a team consisting of Neil Robertson from The Ohio State University; Daniel P. Sanders, a graduate student at the Georgia Institute of Technology; Paul Seymour of Bellcore; and Robin Thomas from Georgia Tech announced a new proof of the Four Color Theorem. However, it still required the use of computers. The proof did gain more widespread acceptance than that of Appel and Haken, in part because the new proof used fewer than half (633) of the number of configurations the Appel-Haken proof used and the computer code was provided online for anyone to verify. While still unsatisfactory to many, the proof by Robertson, et al. was generally accepted, and today the issue of the Four Color Theorem has largely been put to rest. However, many still wonder if anyone will ever find a proof of this simple statement that does not require the assistance of a computer.