Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section9.6Planarity 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.

Subsection9.6.1Planar Graphs

Definition9.6.1Planar 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.

Example9.6.2A 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).

A Planar Graph
Figure9.6.3A Planar Graph

  1. 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.

  2. 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.2 will verify that dense graphs are indeed nonplanar.

  3. 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?

Definition9.6.4Path Graph

A path graph of length \(n\), denoted \(P_n\), is an undirected graph with \(n+1)\) vertices \(v_0, v_1,\dots,\v_n\) with \(n\) edges \(\{v_i,v_{i+1}\}\), \(i=0, 1, n-1\).

Observation9.6.5Graphs 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 vertix, and path graphs, as shown in Figure 9.6.6.

One dimensional graphs
Figure9.6.6One 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 \(K_{3,3}\). This graph is one of two fundamental nonplanar graphs. The Kuratowski Reduction Theorem states that if a graph is nonplanar then “contains” either a \(K_{3,3}\) or a \(K_5\). 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.

The Three Utilities Puzzle
Figure9.6.7The 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.

Task9.6.1

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.

Proof
Proof
Remark9.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\text{,}\) as \(v\) increases, planar graphs are more and more sparse.

The following theorem will be useful as we turn to graph coloring.

Proof

Subsection9.6.2Graph Coloring

A 3-coloring of Euler Island
Figure9.6.13A 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.

Definition9.6.14Graph Coloring

Given an undirected graph \(G = (V, E)\), 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\), \(\chi(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) = \text{blue}\), \(f(2) = \text{red}\), and \(f(3) = f(5) = f(7) = \text{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.

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.

Proof
Definition9.6.17Bipartite 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.

Example9.6.18A Few Examples

  1. 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.

  2. For \(n\geq 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.

  3. 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.

Proof

Subsection9.6.3Exercises for Section 9.6

1

Apply Theorem 9.6.2 to prove that once \(n\) gets to a certain size, a \(K_n\) is nonplanar. What is the largest complete planar graph?

Answer
2

Can you apply Theorem 9.6.2 to prove that the Three Utilities Puzzle can't be solved?

3

What are the chromatic numbers of the following graphs?

What are the chromatic numbers?
Figure9.6.20What are the chromatic numbers?
Answer
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)\), \(n\geq 1\)?

Answer
6

What is the chromatic number of the United States?

7

Complete the proof of Theorem 9.6.8.

Answer
8

Use the outline of a proof of Theorem 9.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\), 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.

Answer
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.

Answer
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?

Answer
14

  1. 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.

  2. 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.