Planarity and Colorings
Annotating a graph so that it contains additional information is very important as the complexity of an application increases. Generally, the more complex the technology, the more precise needs to be its descriptive information.
9.6 Planarity and Colorings
The topics in this section are related to how graphs are drawn.
Planarity: Can a given graph be drawn in a plane so that no edges intersect? Certainly, it is natural to avoid intersections, but up to now we haven't gone out of our way to do so.
Colorings: Suppose that each vertex in an undirected graph is to be colored so that no two vertices that are connected by an edge have the same color. How many colors are needed? This question is motivated by the problem of drawing a map so that no two bordering countries are colored the same. A similar question can be asked for coloring edges.
9.6.1 Planar Graphs
Definition 9.6.1 Planar Graph/Plane Graph. A graph is planar if it can be drawn in a plane so that no edges cross. If a graph is drawn so that no edges intersect, it is a plane graph, and such a drawing is a planar embedding of the graph.
Example 9.6.2 A Planar Graph. The graph in Figure 9.6.3(a) is planar but not a plane graph. The same graph is drawn as a plane graph in Figure 9.6.3(b).
Figure 9.6.3 A Planar Graph
(a) In discussing planarity, we need only consider simple undirected graphs with no self-loops. All other graphs can be treated as such since all of the edges that relate any two vertices can be considered as one "package" that clearly can be drawn in a plane.
(b) Can you think of a graph that is not planar? How would you prove that it isn't planar? Proving the nonexistence of something is usually more difficult than proving its existence. This case is no exception. Intuitively, we would expect that sparse graphs would be planar and dense graphs would be nonplanar. Theorem 9.6.10 will verify that dense graphs are indeed nonplanar.
(c) The topic of planarity is a result of trying to restrict a graph to two dimensions. Is there an analogous topic for three dimensions? What graphs can be drawn in one dimension?
Definition 9.6.4 Path Graph. A path graph of length n, denoted Pn , is an undirected graph with n + 1 vertices v0, v1, . . . , vn having n edges {vi, vi + 1}, i = 0 , 1, . . . , n − 1.
Observation 9.6.5 Graphs in other dimensions. If a graph has only a finite number of vertices, it can always be drawn in three dimensions with no edge crossings. Is this also true for all graphs with an infinite number of vertices? The only "one-dimensional" graphs are graphs consisting of a single vertex, and path graphs, as shown in Figure 9.6.6.
Figure 9.6.6 One dimensional graphs
A discussion of planarity is not complete without mentioning the famous Three Utilities Puzzle. The object of the puzzle is to supply three houses, A, B, and C, with the three utilities, gas, electric, and water. The constraint that makes this puzzle impossible to solve is that no utility lines may intersect. There is no planar embedding of the graph in Figure 9.6.7, which is commonly denoted K3,3 . This graph is one of two fundamental nonplanar graphs. The Kuratowski Reduction Theorem states that if a graph is nonplanar then it "contains" either a K3,3 or a K5. Containment is in the sense that if you start with a nonplanar graph you can always perform a sequence of edge deletions and contractions (shrinking an edge so that the two vertices connecting it coincide) to produce one of the two graphs.
Figure 9.6.7 The Three Utilities Puzzle
A planar graph divides the plane into one or more regions. Two points on the plane lie in the same region if you can draw a curve connecting the two points that does not pass through an edge. One of these regions will be of infinite area. Each point on the plane is either a vertex, a point on an edge, or a point in a region. A remarkable fact about the geography of planar graphs is the following theorem that is attributed to Euler.
Activity 9.6.1
(a) Experiment: Jot down a graph right now and count the number of vertices, regions, and edges that you have. If v + r − e is not 2, then your graph is either nonplanar or not connected.
Theorem 9.6.8 Euler's Formula. If G = (V, E) is a connected planar graph with r regions, v vertices, and e edges, then
v + r − e = 2 (9.6.1)
Proof. We prove Euler's Formula by Induction on e, for e ≥ 0.
Basis: If e = 0, then G must be a graph with one vertex, v = 1; and there is one infinite region, r = 1. Therefore, v + r − e = 1 + 1 − 0 = 2, and the basis is true.
Induction: Suppose that G has k edges, k ≥ 1, and that all connected planar graphs with less than k edges satisfy (9.6.1). Select any edge that is part of the boundary of the infinite region and call it e1. Let G′ be the graph obtained from G by deleting e1. Figure 9.6.9 illustrates the two different possibilities we need to consider: either G ′ is connected or it has two connected components, G1 and G2.
Figure
9.6.9 Two cases in the proof of Euler's Formula
If G′ is connected, the induction hypothesis can be applied to it. If G′ has v′ vertices, r′ edges and e′ edges, then v′ + r′ − e′ = 2 and in terms of the corresponding numbers for G,
v′ = v No vertices were removed to form G′
r′ = r − 1 One region of G was merged with the infinite region when e1 was removed
e′ = k − 1 We assumed that G had k edges.
For the case where G′ is connected,
If G′ is not connected, it must consist of two connected components, G1 and G2, since we started with a connected graph, G. We can apply the induction hypothesis to each of the two components to complete the proof. We leave it to the students to do this, with the reminder that in counting regions, G1 and G2 will share the same infinite region.
Theorem 9.6.10 A Bound on Edges of a Planar Graph. If G = (V, E) is a connected planar graph with v vertices, v ≥ 3, and e edges, then
e ≤ 3v − 6 (9.6.2)
Proof. (Outline of a Proof)
(a) Let r be the number of regions in G. For each region, count the number of edges that comprise its border. The sum of these counts must be at least 3r. Recall that we are working with simple graphs here, so a region made by two edges connecting the same two vertices is not possible.
(b) Based on (a), infer that the number of edges in G must be at least .
(d) Substitute for r in Euler's Formula to obtain an inequality that is
equivalent to (9.6.2)
Remark 9.6.11 One implication of (9.6.2) is that the number of edges in a connected planar graph will never be larger than three times its number of vertices (as long as it has at least three vertices). Since the maximum number of edges in a graph with v vertices is a quadratic function of v, as v increases, planar graphs are more and more sparse.
The following theorem will be useful as we turn to graph coloring.
Theorem 9.6.12 A Vertex of Degree Five. If G is a connected planar graph, then it has a vertex with degree 5 or less.
Proof. (by contradiction): We can assume that G has at least seven vertices, for otherwise the degree of any vertex is at most 5. Suppose that G is a connected planar graph and each vertex has a degree of 6 or more. Then, since
e
ach edge contributes to the degree of two vertices, . However, Theorem 9.6.10 states that the
e ≤ 3v −
6
< 3v, which is a contradiction.
9.6.2 Graph Coloring
Figure 9.6.13 A 3-coloring of Euler Island
The map of Euler Island in Figure 9.6.13 shows that there are seven towns on the island. Suppose that a cartographer must produce a colored map in which no two towns that share a boundary have the same color. To keep costs down, she wants to minimize the number of different colors that appear on the map. How many colors are sufficient? For Euler Island, the answer is three. Although it might not be obvious, this is a graph problem. We can represent the map with a graph, where the vertices are countries and an edge between two vertices indicates that the two corresponding countries share a boundary of positive length. This problem motivates a more general problem.
Definition 9.6.14 Graph Coloring. Given an undirected graph G = (V, E), find a "coloring function" f from V into a set of colors H such that (vi, vj) ∈ E ⇒ f(vi) ≠ f(vj) and H has the smallest possible cardinality. The cardinality of H is called the chromatic number of G , χ(G).
- A coloring function onto an n-element set is called an n-coloring.
- In terms of this general problem, the chromatic number of the graph of Euler Island is three. To see that no more than three colors are needed, we need only display a 3-coloring: f(1) = f(4) = f(6) = blue, f(2) = red, and f(3) = f(5) = f(7) = white. This coloring is not unique. The next smallest set of colors would be of two colors, and you should be able to convince yourself that no 2-coloring exists for this graph.
In the mid-nineteenth century, it became clear that the typical planar graph had a chromatic number of no more than 4. At that point, mathematicians attacked the Four-Color Conjecture, which is that if G is any planar graph, then its chromatic number is no more than 4. Although the conjecture is quite easy to state, it took over 100 years, until 1976, to prove the conjecture in the affirmative.
Theorem 9.6.15 The Four-Color Theorem. If G is a planar graph, then χ(G) ≤ 4.
A proof of the Four-Color Theorem is beyond the scope of this text, but we can prove a theorem that is only 25 percent inferior.
Theorem 9.6.16 The Five-Color Theorem. If G is a planar graph, then χ(G) ≤ 5.
Proof. The number 5 is not a sharp upper bound for χ(G) because of the Four-Color Theorem.
This is a proof by Induction on the Number of Vertices in the Graph. Basis: Clearly, a graph with one vertex has a chromatic number of 1. Induction: Assume that all planar graphs with n − 1 vertices have a chromatic number of 5 or less. Let G be a planar graph. By Theorem 9.6.12, there exists a vertex v with deg v ≤ 5. Let G − v be the planar graph obtained by deleting v and all edges that connect v to other vertices in G. By the induction hypothesis, G − v has a 5-coloring. Assume that the colors used are red, white, blue, green, and yellow.
If deg v < 5, then we can produce a 5-coloring of G by selecting a color that is not used in coloring the vertices that are connected to v with an edge in G.
If deg v = 5, then we can use the same approach if the five vertices that are adjacent to v are not all colored differently. We are now left with the possibility that v1, v2, v3, v4, and v5 are all connected to v by an edge and they are all colored differently. Assume that they are colored red, white blue, yellow, and green, respectively, as in Figure 9.6.17.
Figure 9.6.17
Starting at v1 in G − v, suppose we try to construct a path v3 that passes through only red and blue vertices. This can either be accomplished or it can't be accomplished. If it can't be done, consider all paths that start at v1, and go through only red and blue vertices. If we exchange the colors of the vertices in these paths, including v1 we still have a 5-coloring of G − v. Since v1 is now blue, we can color the central vertex, v, red.
Finally, suppose that v1 is connected to v3 using only red and blue vertices. Then a path from v1 to v3 by using red and blue vertices followed by the edges (v3, v) and (v, v1) completes a circuit that either encloses v2 or encloses v4 and v5. Therefore, no path from v2 to v4 exists using only white and yellow vertices. We can then repeat the same process as in the previous paragraph with v2 and v4, which will allow us to color v white.
Definition 9.6.18 Bipartite Graph. A bipartite graph is a graph that has a 2-coloring. Equivalently, a graph is bipartite if its vertices can be partitioned into two nonempty subsets so that no edge connects vertices from the same subset.
Example 9.6.19 A Few Examples.
(a) The graph of the Three Utilities Puzzle is bipartite. The vertices are partitioned into the utilities and the homes. Of course a 2-coloring of the graph is to color the utilities red and the homes blue.
(b) For n ≥ 1, the n-cube is bipartite. A coloring would be to color all strings with an even number of 1's red and the strings with an odd number of 1's blue. By the definition of the n-cube, two strings that have the same color couldn't be connected since they would need to differ in at least two positions.
(c) Let V be a set of 64 vertices, one for each square on a chess board.
We can index the elements of V by
vij = the square on the row i, column j. Connect vertices in V according to whether or not you can move a knight from one square to another. Using our indexing of V, (
vij, vkl)
∈ E if and only if
is a bipartite graph. The usual coloring of a chessboard is valid 2-coloring.
How can you recognize whether a graph is bipartite? Unlike planarity, there is a nice equivalent condition for a graph to be bipartite.
Theorem 9.6.20 No Odd Circuits in a Bipartite Graph. An undirected graph is bipartite if and only if it has no circuit of odd length.
Proof. (⇒) Let G = (V, E) be a bipartite graph that is partitioned into two sets, R(ed) and B(lue) that define a 2-coloring. Consider any circuit in V . If we specify a direction in the circuit and define f on the vertices of the circuit by
f (u) = the next vertex in the circuit after v
Note that f is a bijection. Hence the number of red vertices in the circuit equals the number of blue vertices, and so the length of the circuit must be even.
(⇐ = ) Assume that G has no circuit of odd length. For each component of G, select any vertex w and color it red. Then for every other vertex v in the component, find the path of shortest distance from w to v . If the length of the path is odd, color v blue, and if it is even, color v red. We claim that this method defines a 2-coloring of G. Suppose that it does not define a 2-coloring.
Then let va and vb be two vertices with identical colors that are connected with an edge. By the way that we colored G, neither v a nor vb could equal w. We can now construct a circuit with an odd length in G. First, we start at w and follow the shortest path to va. Then follow the edge ( va, vb), and finally, follow the reverse of a shortest path from w to vb . Since v a and vb have the same color, the first and third segments of this circuit have lengths that are both odd or even, and the sum of their lengths must be even. The addition of the single edge (va, vb ) shows us that this circuit has an odd length. This contradicts our premise.
Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.