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

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.

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.

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

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

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\).

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.

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.

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.

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.

If \(G = (V, E)\) is a connected planar graph with \(r\) regions, \(v\) vertices and \(e\) edges, then \begin{gather} v + r - e = 2\label{euler-formula}\tag{9.6.1} \end{gather}

If \(G = (V, E)\) is a connected planar graph with \(v\) vertices, \(v\geq 3\), and \(e\) edges, then \begin{gather} e \leq 3v - 6\label{edge-bound}\tag{9.6.2} \end{gather}

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.

If \(G\) is a connected planar graph, then it has a vertex with degree 5 or less.

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.

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.

If \(G\) is a planar graph, then \(\chi (G)\leq 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.

If \(G\) is a planar graph, then \(\chi (G)\leq 5\).

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.

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\), 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\), 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\), \(\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.

An undirected graph is bipartite if and only if it has no circuit of odd length.

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?

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

What are the chromatic numbers of the following graphs?

AnswerProve that if an undirected graph has a subgraph that is a \(K_3\) it then its chromatic number is at least 3.

What is \(\chi \left(K_n\right)\), \(n\geq 1\)?

AnswerWhat is the chromatic number of the United States?

Complete the proof of Theorem 9.6.8.

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

Let \(G = (V,E)\) with \(|V|\geq 11\), and let \(U\) be the set of all undirected edges between distinct vertices in \(V\). Prove that either \(G\) or \(G' = \left(V,E^c\right)\) is nonplanar.

AnswerDesign an algorithm to determine whether a graph is bipartite.

Prove that a bipartite graph with an odd number of vertices greater than or equal to 3 has no Hamiltonian circuit.

AnswerProve that any graph with a finite number of vertices can be drawn in three dimensions so that no edges intersect.

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?

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

Graph Coloring WeBWork Exercise