Section 13.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.
Subsection 13.6.1 Planar Graphs
¶Definition 13.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 13.6.2. A Planar Graph.
The graph in Figure 13.6.3(a) is planar but not a plane graph. The same graph is drawn as a plane graph in Figure 13.6.3(b).
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.
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 13.6.10 will verify that dense graphs are indeed nonplanar.
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 13.6.4. Path Graph.
A path graph of length \(n\text{,}\) denoted \(P_n\text{,}\) is an undirected graph with \(n+1\) vertices \(v_0, v_1,\dots, v_n\) having \(n\) edges \(\{v_i,v_{i+1}\}\text{,}\) \(i=0, 1, \dots, n-1\text{.}\)
Observation 13.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 13.6.6.
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 13.6.7, which is commonly denoted \(K_{3,3}\text{.}\) 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 \(K_{3,3}\) or a \(K_5\text{.}\) 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.
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 13.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 13.6.8. Euler's Formula.
If \(G = (V, E)\) is a connected planar graph with \(r\) regions, \(v\) vertices, and \(e\) edges, then
Proof.
We prove Euler's Formula by Induction on \(e\text{,}\) for \(e \geq 0\text{.}\)
Basis: If \(e = 0\text{,}\) then \(G\) must be a graph with one vertex, \(v = 1\text{;}\) and there is one infinite region,\(\text{ }r = 1\text{.}\) Therefore, \(v + r-e= 1 + 1-0 = 2\text{,}\) and the basis is true.
Induction: Suppose that \(G\) has \(k\) edges, \(k \geq 1\text{,}\) and that all connected planar graphs with less than \(k\) edges satisfy (13.6.1). Select any edge that is part of the boundary of the infinite region and call it \(e_1\text{.}\) Let \(G'\) be the graph obtained from \(G\) by deleting \(e_1\text{.}\) Figure 13.6.9 illustrates the two different possibilities we need to consider: either \(G'\) is connected or it has two connected components, \(G_1\) and \(G_2\text{.}\)
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\text{,}\)
For the case where \(G'\) is connected,
If \(G'\) is not connected, it must consist of two connected components, \(G_1\) and \(G_2\text{,}\) since we started with a connected graph, \(G\text{.}\) 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, \(G_1\) and \(G_2\) will share the same infinite region.
Theorem 13.6.10. A Bound on Edges of a Planar Graph.
If \(G = (V, E)\) is a connected planar graph with \(v\) vertices, \(v\geq 3\text{,}\) and \(e\) edges, then
Proof.
(Outline of a Proof)
Let \(r\) be the number of regions in \(G\text{.}\) For each region, count the number of edges that comprise its border. The sum of these counts must be at least \(3r\text{.}\) Recall that we are working with simple graphs here, so a region made by two edges connecting the same two vertices is not possible.
Based on (a), infer that the number of edges in \(G\) must be at least \(\frac{3 r}{2}\text{.}\)
\(e\geq \frac{3r}{2}\text{ }\Rightarrow \text{ }r\leq \frac{2e}{3}\)
Substitute \(\frac{2e}{3}\) for \(r\) in Euler's Formula to obtain an inequality that is equivalent to (13.6.2)
Remark 13.6.11.
One implication of (13.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\text{,}\) as \(v\) increases, planar graphs are more and more sparse.
The following theorem will be useful as we turn to graph coloring.
Theorem 13.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 each edge contributes to the degree of two vertices, \(e\geq \frac{6v}{2}=3v\text{.}\) However, Theorem 13.6.10 states that the \(e\leq 3v-6 < 3v\text{,}\) which is a contradiction.
Subsection 13.6.2 Graph Coloring
¶
The map of Euler Island in Figure 13.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 13.6.14. Graph Coloring.
Given an undirected graph \(G = (V, E)\text{,}\) find a “coloring function” \(f\) from \(V\) into a set of colors \(H\) such that \(\left(v_i,v_j\right)\in E \Rightarrow f\left(v_i\right)\neq f\left(v_j\right)\) and \(H\) has the smallest possible cardinality. The cardinality of \(H\) is called the chromatic number of \(G\text{,}\) \(\chi(G)\text{.}\)
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) = \text{blue}\text{,}\) \(f(2) = \text{red}\text{,}\) and \(f(3) = f(5) = f(7) = \text{white}\text{.}\) 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 13.6.15. The Four-Color Theorem.
If \(G\) is a planar graph, then \(\chi (G)\leq 4\text{.}\)
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 13.6.16. The Five-Color Theorem.
If \(G\) is a planar graph, then \(\chi (G)\leq 5\text{.}\)
Proof.
The number 5 is not a sharp upper bound for \(\chi(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 13.6.12, there exists a vertex \(v\) with \(\deg v \leq 5\text{.}\) Let \(G - v\) be the planar graph obtained by deleting \(v\) and all edges that connect \(v\) to other vertices in \(G\text{.}\) 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\text{,}\) 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\text{.}\)
If \(\deg v = 5\text{,}\) 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 \(v_1\text{,}\) \(v_2\text{,}\) \(v_3\text{,}\) \(v_4\text{,}\) and \(v_5\) 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 13.6.17.
Starting at \(v_1\) in \(G-v\text{,}\) suppose we try to construct a path \(v_3\) 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 \(v_1\text{,}\) and go through only red and blue vertices. If we exchange the colors of the vertices in these paths, including \(v_1\) we still have a 5-coloring of \(G - v\text{.}\) Since \(v_1\) is now blue, we can color the central vertex, \(v\text{,}\) red.
Finally, suppose that \(v_1\) is connected to \(v_3\) using only red and blue vertices. Then a path from \(v_{1 }\) to \(v_3\) by using red and blue vertices followed by the edges \(\left(v_3,v\right)\) and \(\left(v,v_1\right)\) completes a circuit that either encloses \(v_2\) or encloses \(v_4\) and \(v_5\text{.}\) Therefore, no path from \(v_2\) to \(v_4\) exists using only white and yellow vertices. We can then repeat the same process as in the previous paragraph with \(v_2\) and \(v_4\text{,}\) which will allow us to color v white.
Definition 13.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 13.6.19. A Few Examples.
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.
For \(n\geq 1\text{,}\) 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.
Let \(V\) be a set of 64 vertices, one for each square on a chess board. We can index the elements of \(V\) by \(\quad \quad\)\(v_{i j}\) = the square on the row \(i\text{,}\) column \(j\text{.}\) Connect vertices in \(V\) according to whether or not you can move a knight from one square to another. Using our indexing of \(V\text{,}\) \(\quad \quad\)\(\left(v_{i j}, v_{k l}\right)\in E\text{ if and only if } \begin{array}{c} |i-k|+|j-l|=3 \\ \text{and } |i-k|\cdot |j-l|=2 \\ \end{array}\) \((V, E)\) 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 13.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.
(\(\Rightarrow\)) 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\text{.}\) If we specify a direction in the circuit and define \(f\) on the vertices of the circuit by
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.
(\(\Longleftarrow\)) Assume that \(G\) has no circuit of odd length. For each component of \(G\text{,}\) 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\text{.}\) 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\text{.}\) Suppose that it does not define a 2-coloring. Then let \(v_a\) and \(v_b\) be two vertices with identical colors that are connected with an edge. By the way that we colored \(G\text{,}\) neither \(v_a\) nor \(v_{b }\) could equal \(w\text{.}\) We can now construct a circuit with an odd length in \(G\text{.}\) First, we start at \(w\) and follow the shortest path to \(v_a\) . Then follow the edge \(\left(v_a,v_b\right)\text{,}\) and finally, follow the reverse of a shortest path from \(w\) to \(v_b\text{.}\) Since \(v_a\) and \(v_b\) 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 \(\left(v_a,v_b\right)\) shows us that this circuit has an odd length. This contradicts our premise.
Exercises 13.6.3 Exercises
¶1.
Apply Theorem 13.6.12 to prove that once \(n\) gets to a certain size, a \(K_n\) is nonplanar. What is the largest complete planar graph?
Theorem 13.6.12 can be applied to infer that if \(n\geqslant 5\text{,}\) then \(K_n\) is nonplanar. A \(K_4\) is the largest complete planar graph.
2.
Can you apply Theorem 13.6.12 to prove that the Three Utilities Puzzle can't be solved?
3.
What are the chromatic numbers of the following graphs?
4
3
3
3
2
4
4.
Prove that if an undirected graph has a subgraph that is a \(K_3\) it then its chromatic number is at least 3.
5.
What is \(\chi \left(K_n\right)\text{,}\) \(n\geq 1\text{?}\)
The chromatic number is \(n\) since every vertex is connected to every other vertex.
6.
What is the chromatic number of the United States?
7.
Complete the proof of Euler's Formula.
Suppose that \(G'\) is not connected. Then \(G'\) is made up of 2 components that are planar graphs with less than \(k\) edges, \(G_1\) and \(G_2\text{.}\) For \(i=1,2\) let \(v_i,r_i, \text{and} e_i\) be the number of vertices, regions and edges in \(G_i\text{.}\) By the induction hypothesis, \(v_i+r_i-e_i=2\) for \(i=1,2\text{.}\)
One of the regions, the infinite one, is common to both graphs. Therefore, when we add edge \(e\) back to the graph, we have \(r=r_1+r_2-1\text{,}\) \(v=v_1+v_2\text{,}\) and \(e=e_1+e_2+1\text{.}\)
8.
Use the outline of a proof of Theorem 13.6.10 to write a complete proof. Be sure to point out where the premise \(v\geq 3\) is essential.
9.
Let \(G = (V,E)\) with \(|V|\geq 11\text{,}\) and let \(U\) be the set of all undirected edges between distinct vertices in \(V\text{.}\) Prove that either \(G\) or \(G' = \left(V,E^c\right)\) is nonplanar.
Since \(\left| E\right| +E^c=\frac{n(n-1)}{2}\text{,}\) either \(E \text{ or } E^c\) has at least \(\frac{n(n-1)}{4}\) elements. Assume that it is \(E\) that is larger. Since \(\frac{n(n-1)}{4}\) is greater than \(3n-6\text{ }\text{for}\text{ }n\geqslant 11\text{,}\) \(G\) would be nonplanar. Of course, if \(E^c\) is larger, then \(G'\) would be nonplanar by the same reasoning. Can you find a graph with ten vertices such that it is planar and its complement is also planar?
10.
Design an algorithm to determine whether a graph is bipartite.
11.
Prove that a bipartite graph with an odd number of vertices greater than or equal to 3 has no Hamiltonian circuit.
Suppose that \((V,E)\) is bipartite (with colors red and blue), \(\left| E\right|\) is odd, and \(\left(v_1,v_2,\ldots ,v_{2n+1},v_1\right)\) is a Hamiltonian circuit. If \(v_1\) is red, then \(v_{2n+1}\) would also be red. But then \(\left\{v_{2n+1},v_1\right\}\) would not be in \(E\text{,}\) a contradiction.
12.
Prove that any graph with a finite number of vertices can be drawn in three dimensions so that no edges intersect.
13.
Suppose you had to color the edges of an undirected graph so that for each vertex, the edges that it is connected to have different colors. How can this problem be transformed into a vertex coloring problem?
Draw a graph with one vertex for each edge, If two edges in the original graph meet at the same vertex, then draw an edge connecting the corresponding vertices in the new graph.
14.
Suppose the edges of a \(K_6\) are colored either red or blue. Prove that there will be either a “red \(K_3\)” (a subset of the vertex set with three vertices connected by red edges) or a “blue \(K_3\)” or both.
Suppose six people are selected at random. Prove that either there exists a subset of three of them with the property that any two people in the subset can communicate in a common language, or there exist three people, no two of whom can communicate in a common language.
15.
Let \(d\) be a positive integer, and let \(a_1, a_2, \dots a_d\) be positive integers greater than or equal to two. The mesh graph \(M(a_1,a_2,\dots,a_d)\) has vertices of the form \(x=(x_1, x_2,\dots, x_d)\) where \(1 \leq x_i \leq a_i\text{.}\) Two vertices \(x\) and \(y\) are adjacent if and only if \(\sum_{i=1}^{d}{\lvert x_i-y_i \rvert} = 1\text{.}\) In other words, two adjacent vertices must differ in only one coordinate and by a difference of 1.
What is the chromatic number of \(M(a_1,a_2,\dots,a_d)\text{?}\)
For what pairs \((a_1, a_2)\) does \(M(a_1, a_2)\) have a Hamiltonian circuit?
For what triples \((a_1, a_2, a_3)\) does \(M(a_1, a_2, a_3)\) have a Hamiltonian circuit?