ads Planarity and Colorings

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

🔗

Subsection 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. A drawing of a graph on the plane such that there are no edge crossings is called a planar embedding of the graph, or a plane graph for short.

Example 9.6.2. A Planar Graph.

The graph in Figure 9.6.3(a) is planar but the drawing of it is not a plane graph. The drawing of the same graph in Figure 9.6.3(b) is a planar graph.

On the left of the figure is a graph labeled (a) that has two edges crossing and so it is not a plane graph. That graph is planar and to the right a graph labeled (b) is redrawn and is planar embedding, having no edge crossings. The graph is defined in SageMath as Graph({1:[2,3],2:[3,4]}). — Figure 9.6.3. A planar graph and a planar embedding that graph.

🔗

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 “bundle” 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.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 9.6.4. Path 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}

having

n

edges

{v_{i}, v_{i + 1}},

i = 0, 1, \dots, 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.

🔗

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 it “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.

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

🔗

G = (V, E)

is a connected planar graph with

r

regions,

v

vertices, and

e

edges, then

\begin{matrix} (9.6.1) & v + r - e = 2 \end{matrix}

Proof.

We prove Euler’s Formula by Induction on

e,

for

e \geq 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 \geq 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

e_{1} .

Let

G^{'}

be the graph obtained from

G

by deleting

e_{1} .

Figure 9.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} .

Figure 9.6.9. Two cases in the proof of Euler’s Formula

G^{'}

is connected, the induction hypothesis can be applied to it. If

G^{'}

has

v^{'}

vertices,

r^{'}

regions and

e^{'}

edges, then

v^{'} + r^{'} - e^{'} = 2

and in terms of the corresponding numbers for

G,

\begin{array}{ll} v^{'} = v & No vertices were removed to form G^{'} \\ r^{'} = r - 1 & One region of G was merged with the infinite region when e_{1} was removed \\ e^{'} = k - 1 & We assumed that G had k edges. \end{array}

For the case where

G^{'}

is connected,

\begin{aligned} v + r - e & = v + r - k \\ = v^{'} + (r^{'} + 1) - (e^{'} + 1) \\ = v^{'} + r^{'} - e^{'} \\ = 2 \end{aligned}

G^{'}

is not connected, it must consist of two connected components,

G_{1}

and

G_{2},

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,

G_{1}

and

G_{2}

will share the same infinite region.

🔗

Theorem 9.6.10. A Bound on Edges of a Planar Graph.

🔗

G = (V, E)

is a connected planar graph with

v

vertices,

v \geq 3,

and

e

edges, then

\begin{matrix} (9.6.2) & e \leq 3 v - 6 \end{matrix}

Proof.

(Outline of a Proof)

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 $3 r .$ 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} .$
$e \geq \frac{3 r}{2} \Rightarrow r \leq \frac{2 e}{3}$
Substitute $\frac{2 e}{3}$ 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,

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.

🔗

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{6 v}{2} = 3 v .

However, Theorem 9.6.10 states that the

e \leq 3 v - 6 < 3 v,

which is a contradiction.

🔗

Subsection 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. The graph corresponding to the map of Euler Island is Figure 9.6.14.

Graph({1:[2,5],2:[3,5,6,4,7], 3:[4],4:[7],7:[6],5:[6]}) — 🔗
Figure 9.6.14. The graph of Euler Island

🔗

The problem of coloring Euler Island motivates a more general problem.

🔗

Definition 9.6.15. Graph Coloring.

🔗

Given an undirected graph

G = (V, E),

find a “coloring function”

f

from

V

into a set of colors

H

such that

(v_{i}, v_{j}) \in E \Rightarrow f (v_{i}) \neq f (v_{j})

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.16. The Four-Color Theorem.

🔗

G

is a planar graph, then

χ (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.

🔗

Theorem 9.6.17. The Five-Color Theorem.

🔗

G

is a planar graph, then

χ (G) \leq 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 \leq 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.

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

\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

v_{1},

v_{2},

v_{3},

v_{4},

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

Figure used in the proof of the five color theorem — Figure 9.6.18.

Starting at

v_{1}

G - v,

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},

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 .

Since

v_{1}

is now blue, we can color the central vertex,

v,

red.

Finally, suppose that

v_{1}

is connected to

v_{3}

using only red and blue vertices. Then a path from

v_{1}

v_{3}

by using red and blue vertices followed by the edges

(v_{3}, v)

and

(v, v_{1})

completes a circuit that either encloses

v_{2}

or encloses

v_{4}

and

v_{5} .

Therefore, no path from

v_{2}

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},

which will allow us to color

v_{4}

white.

🔗

Definition 9.6.19. 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.20. A Few Examples.

The graph of the Three Utilities Puzzle is bipartite. The vertices are partitioned into the utilities and the homes. 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 $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,$ $(v_{i j}, v_{k l}) \in E if and only if \begin{matrix} | i - k | + | j - l | = 3 \\ and | i - k | \cdot | j - l | = 2 \end{matrix}$ $(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? There is a nice equivalent condition for a graph to be bipartite.

🔗

Theorem 9.6.21. 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 .

If we specify a direction in the circuit and define

f

on the vertices of the circuit by

f (v) = 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

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

v_{a}

and

v_{b}

be two vertices with identical colors that are connected with an edge. By the way that we colored

G,

neither

v_{a}

nor

v_{b}

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

v_{a}

. Then follow the edge

(v_{a}, v_{b}),

and finally, follow the reverse of a shortest path from

w

v_{b} .

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

(v_{a}, v_{b})

shows us that this circuit has an odd length. This contradicts our premise.

🔗

Exercises 9.6.3 Exercises

🔗

1.

🔗

Use Euler’s formula to prove by contradiction that a

K_{5}

is nonplanar. This shows that a

K_{4}

is the largest complete graph that is planar.

Answer.

K_{5}

has 10 edges. If a

K_{5}

is planar, the number of regions into which the plane is divided must be 7, by Euler’s formala (

5 + 7 - 10 = 2

). If we re-count the edges of the graph by counting the number edges bordering the regions we get a count of at least

7 \times 3 = 21 .

But we’ve counted each edge twice this way and the count must be even. This implies that the number of edges is at least 11, which a contradiction.

🔗

2.

🔗

Use Euler’s formula to prove by contradiction that a

K_{3, 3}

is nonplanar.

Hint.

Don’t forget Theorem 9.6.21!

🔗

3.

🔗

What are the chromatic numbers of the following graphs?

Answer.

🔗

4.

🔗

A connected planar graph has

2001

vertices and divides the plane into

1024

regions. How many edges does it have?

🔗

5.

🔗

What is

χ (K_{n}),

n \geq 1 ?

Answer.

The chromatic number is

n

since every vertex is connected to every other vertex.

🔗

6.

🔗

Suppose that all of the vertices of connected planar graph have degree 3 and that there are 20 vertices. How many edges and regions does this graph have?

🔗

7.

🔗

Complete the proof of Euler’s Formula.

Answer.

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

For

i = 1, 2

let

v_{i}, r_{i}, and e_{i}

be the number of vertices, regions and edges in

G_{i} .

By the induction hypothesis,

v_{i} + r_{i} - e_{i} = 2

for

i = 1, 2 .

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,

v = v_{1} + v_{2},

and

e = e_{1} + e_{2} + 1 .

\begin{aligned} v + r - e & = (v_{1} + v_{2}) + (r_{1} + r_{2} - 1) - (e_{1} + e_{2} + 1) \\ = (v_{1} + r_{1} - e_{1}) + (v_{2} + r_{2} - e_{2}) - 2 \\ = 2 + 2 - 2 \\ = 2 \end{aligned}

🔗

8.

🔗

A graph is said to be a perfect graph if its chromatic number is

n

and it contains a

K_{n}

as a subgraph. For example, a cycle graph of length 5 is not perfect because its chromatic number is three but it has no

K_{3}

as a subgraph. Find a graph with chromatic number four that is not perfect.

🔗

9.

🔗

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

G^{'} = (V, E^{c})

is nonplanar.

Answer.

Since

| E | + | E^{c} | = \frac{n (n - 1)}{2},

either

E 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

3 n - 6 for n ⩾ 11,

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.

Answer.

Suppose that

(V, E)

is bipartite (with colors red and blue),

| E |

is odd, and

(v_{1}, v_{2}, \dots, v_{2 n + 1}, v_{1})

is a Hamiltonian circuit. If

v_{1}

is red, then

v_{2 n + 1}

would also be red. But then

{v_{2 n + 1}, v_{1}}

would not be in

E,

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?

Answer.

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

Two vertices

x

and

y

are adjacent if and only if

\sum_{i = 1}^{d} | x_{i} - y_{i} | = 1 .

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}) ?$
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?

Solution.

The chromatic number will always be two. One coloring of any of these graphs would be to color all vertices whose coordinate add up to an even integer one color and the other vertices whose coordinates have an odd sum some other color. This works because for any vertex, if the sum of coordinate is even, the adjacent vertices differ in exactly one coordinate by $\pm 1$ and so they have a coordinate sum that is odd.
If both $a_{1}$ and $a_{2}$ are odd, then $M (a_{1}, a_{2})$ does not have a Hamiltonian circuit. To see why, we can color vertices with an even coordinate sum white and the ones with a odd sum black. If $a_{1} = 2 k_{1} + 1$ and $a_{2} = 2 k_{2} + 1,$ then there are $N = 4 k_{1} k_{2} + 2 k_{1} + 2 k_{2} + 1$ vertices. There will be $k_{1} k_{2} + k_{1} + k_{2} + 1$ white vertices and one fewer black one. Any circuit that starts and ends at any vertex must have an even number of vertices if we count the beginning/ending vertex once. This implies that a Hamiltonian circuit that includes all vertices cannot exist.

If either of the $a_{i}$ are even, $M (a_{1}, a_{2})$ does have a Hamiltonian circuit. There are many different possible circuits, but one of them, assuming $a_{1}$ is even, would be to start at $(1, 1),$ traverse the left border, the top border and the right border, leaving you at $(a_{1}, 1) .$ then you can zig-zag back to $(1, 1)$ visiting all of the vertices in the interior of the graph and the bottom border. This is is illustrated in the following graph of $M (4, 3)$

A Hamiltonian circuit of $M (4, 3)$ as described in the text.
As in the two diminsional case there will be a Hamiltonian circuit if at least one of the $a_{i}$ are even.

🔗

References 9.6.4 Further Reading

🔗

[1]

Wilson, R., Four Colors Suffice - How the Map Problem Was SolvedPrinceton, NJ: Princeton U. Press, 2013.

You have attempted of activities on this page.

Prev Top Next