Planarity and Graph Coloring

The Central Idea

Planarity and coloring are two different structural questions.

Planarity asks:

Graph coloring asks:

Both problems depend on graph structure rather than on one particular drawing.

What Is a Planar Graph?

A graph is planar if it can be drawn in the plane so that edges meet only at common endpoints.

Edge crossings that occur merely because of a poor drawing do not make the graph nonplanar.

Planar Graph versus Planar Drawing

The graph itself is called planar when at least one crossing-free drawing exists.

A particular crossing-free representation is called a planar embedding or plane graph.

Thus, planarity is a property of the abstract graph, while a planar embedding is one concrete realization of that property.

A Crossing Does Not Automatically Mean Nonplanar

A graph may be drawn with crossing edges even though another drawing avoids all crossings.

Therefore, seeing a crossing in one picture proves only that the drawing has a crossing.

It does not prove that the graph is nonplanar.

Example: A Redrawable Crossing

Consider a cycle on four vertices with both horizontal and diagonal-looking placements. A drawing may visually cross edges depending on where the vertices are placed.

Since a simple four-cycle can be drawn as a square,

it is planar.

Faces of a Plane Graph

A planar embedding divides the plane into regions called faces.

The unbounded region outside the drawing also counts as a face.

If \(F\) denotes the number of faces, then every planar embedding has one outer face plus any bounded interior faces.

A Simple Plane Graph

Euler's Formula for Planar Graphs

For a connected plane graph,

where

• \(V\) is the number of vertices;
• \(E\) is the number of edges;
• \(F\) is the number of faces, including the outer face.

Example: Using Euler's Formula

The plane graph above has

and

Therefore,

Solving gives

There are two bounded triangular faces and one outer face.

Why Euler's Formula Matters

Euler's formula connects three structural counts that may appear unrelated: vertices, edges, and faces.

It can be used to verify a planar embedding and to derive restrictions that every simple planar graph must satisfy.

An Edge Bound for Simple Planar Graphs

If a simple connected planar graph has

then

This gives a useful necessary condition for planarity.

Why the Bound Appears

In a simple planar graph with at least three vertices, every face boundary uses at least three edge appearances.

Counting edge appearances around faces gives

Combining this with

yields

The Edge Bound Is Necessary, Not Sufficient

If a simple graph violates

then it is definitely nonplanar.

But satisfying the inequality does not guarantee planarity.

The Complete Graph \(K_5\)

The complete graph \(K_5\) has

and

A simple planar graph with five vertices could have at most

edges.

Since

\(K_5\) is nonplanar.

Bipartite Planar Edge Bound

A simple bipartite planar graph has no odd cycles, so in particular it has no triangular face.

For \(V\ge3\),

This stronger bound is useful for testing bipartite graphs.

The Complete Bipartite Graph \(K_{3,3}\)

The graph \(K_{3,3}\) has

and

If it were planar and bipartite, we would need

Since

\(K_{3,3}\) is nonplanar.

Two Fundamental Nonplanar Graphs

The graphs

and

play a central role in planarity theory.

More advanced results show that every nonplanar graph contains a structural obstruction related to one of these two graphs.

Subdividing an Edge

To subdivide an edge means to insert a new vertex along that edge.

For example,

can be replaced by

Subdivision changes the vertex and edge counts but preserves the underlying route structure relevant to many planarity questions.

Kuratowski's Theorem

A finite graph is planar if and only if it contains no subgraph that is a subdivision of

or

This gives a complete structural characterization of planarity, although recognizing such subdivisions can require substantial reasoning.

Planarity in Network Design

Planarity matters when physical crossings are expensive, impossible, or undesirable.

Examples include:

• printed circuit layouts;
• transportation planning;
• utility routing;
• geographic subdivision;
• visual network diagrams;
• certain communication and wiring problems.

What Is Graph Coloring?

A vertex coloring assigns a color to every vertex so that adjacent vertices receive different colors.

A coloring satisfying this rule is called a proper vertex coloring.

Colors Are Labels

The word color does not require literal visual colors.

We may use labels such as

or

What matters is whether adjacent vertices receive different labels.

A First Coloring Example

Consider a path

We may color

with one color and

with another.

Thus the path can be properly colored with two colors.

Chromatic Number

The chromatic number of a graph \(G\), written

is the minimum number of colors needed for a proper vertex coloring.

Example: Complete Graphs

In the complete graph \(K_n\), every pair of distinct vertices is adjacent.

Therefore every vertex must receive its own color:

Example: Trees

Every nontrivial tree can be colored with two colors.

Start at any vertex, color it with color 1, color all its neighbors with color 2, and alternate by level.

Therefore, for a tree with at least one edge,

One-Vertex Graph

A graph with one vertex and no edges needs only one color.

Bipartite Graphs and Two-Colorability

A graph is bipartite when its vertices can be divided into two sets so that every edge joins one set to the other.

A graph is bipartite if and only if it can be properly colored with at most two colors.

Odd Cycles Prevent Two-Coloring

A graph is bipartite if and only if it contains no odd cycle.

For example, the triangle

cannot be colored with two colors because alternating colors around the cycle forces the final vertex to conflict with the first.

Chromatic Number of Cycles

For an even cycle,

For an odd cycle,

A Greedy Coloring Strategy

One simple coloring method is:

1. Choose an ordering of the vertices.
2. Process them one at a time.
3. Assign each vertex the first available color not used by its already-colored neighbors.

This produces a proper coloring, though not always one using the minimum possible number of colors.

Vertex Order Can Matter

A greedy coloring may use different numbers of colors depending on the order in which vertices are processed.

Therefore a greedy coloring gives an upper bound on \(\chi(G)\), not automatically the exact chromatic number.

Degree and Coloring

If a graph has maximum degree

then a simple greedy argument gives

This bound is easy to obtain, though often not tight.

Cliques Give Lower Bounds

A clique is a set of vertices that are pairwise adjacent.

If a graph contains a clique of size \(k\), then at least \(k\) colors are necessary.

Thus cliques provide useful lower bounds on the chromatic number.

Coloring Planar Graphs

Every planar graph can be properly colored with at most four colors.

This is the Four Color Theorem.

The Four Color Theorem

The Four Color Theorem states that four colors are sufficient to color the vertices of every planar graph so that adjacent vertices have different colors.

Equivalently, four colors suffice for coloring planar maps when regions sharing a boundary segment must receive different colors.

Map Coloring as Graph Coloring

To convert a map-coloring problem into a graph:

• represent each region by a vertex;
• join two vertices when the corresponding regions share a boundary segment.

A proper vertex coloring of the resulting graph becomes a valid coloring of the map.

Touching at a Point

In standard map coloring, two regions that meet only at a single point are not usually treated as adjacent.

Adjacency normally requires sharing a nonzero boundary segment.

Edge Coloring

Graph coloring can also apply to edges.

In a proper edge coloring, edges sharing a common endpoint must receive different colors.

This lesson focuses primarily on vertex coloring, but the broader coloring framework extends naturally to edges.

Coloring as Scheduling

Suppose vertices represent activities and an edge joins two activities that cannot occur at the same time.

A color can represent a time slot.

Then a proper coloring assigns conflicting activities to different time slots.

Coloring as Resource Assignment

Graph coloring can model many resource-conflict problems.

Examples include:

• exam scheduling;
• frequency assignment;
• register allocation;
• task scheduling;
• map coloring;
• conflict-free grouping.

Planarity and Coloring Are Related but Distinct

Planarity concerns whether a crossing-free embedding exists.

Coloring concerns compatible assignments to adjacent objects.

The Four Color Theorem links the topics because planar structure limits how complicated adjacency can become.

Common Error: Treating One Crossing as Proof of Nonplanarity

A crossing in one drawing may disappear after redrawing the graph.

To prove nonplanarity, one needs a structural argument, not merely an inconvenient picture.

Common Error: Forgetting the Outer Face

When applying Euler's formula,

the unbounded exterior region counts as one face.

Common Error: Using the Planar Edge Bound as a Complete Test

The inequality

is necessary for simple planar graphs with \(V\ge3\), but it is not sufficient.

Passing the inequality does not prove planarity.

Common Error: Allowing Adjacent Vertices to Share a Color

A proper vertex coloring requires

Nonadjacent vertices may share a color.

Common Error: Assuming a Greedy Coloring Is Optimal

A greedy procedure always produces a proper coloring, but it may use more colors than necessary.

The number of colors used by one greedy run is therefore not automatically the chromatic number.

Common Error: Confusing Clique Size with Chromatic Number

A clique of size \(k\) guarantees

But the chromatic number may be larger than the size of a particular clique.

Clique size is a lower bound, not always an exact answer.

A Reliable Procedure for Planarity Problems

1. Ask whether crossings can be removed by redrawing.
2. Count vertices and edges.
3. Apply \(E\le3V-6\) for simple planar candidates with \(V\ge3\).
4. For simple bipartite graphs, apply \(E\le2V-4\).
5. Look for structural obstructions related to \(K_5\) or \(K_{3,3}\).
6. If a planar embedding is available, use Euler's formula as a consistency check.

A Reliable Procedure for Coloring Problems

1. Identify which vertices are adjacent.
2. Look for large cliques to obtain lower bounds.
3. Check whether the graph is bipartite.
4. Use a systematic coloring order.
5. Verify that adjacent vertices differ.
6. Compare the number of colors used with known lower bounds.
7. Distinguish a valid coloring from a proof that the coloring is minimum.

Example: Full Planarity Check

Suppose a simple graph has

and

A simple planar graph with six vertices can have at most

edges.

Since

the graph is nonplanar.

Example: Full Coloring Check

Suppose a graph contains a triangle.

The three vertices of the triangle are pairwise adjacent, so at least three colors are required:

If we then construct a proper coloring of the entire graph using three colors, we can conclude

Practice 1: Planarity Meaning

What must be true for a graph to be planar?

Practice 2: Euler's Formula

A connected plane graph has

Find \(F\).

Practice 3: Planar Edge Bound

A simple graph has \(7\) vertices and \(16\) edges.

Does the bound \(E\le3V-6\) rule out planarity?

Practice 4: \(K_5\)

Why does the inequality \(E\le3V-6\) prove that \(K_5\) is nonplanar?

Practice 5: Proper Coloring

What restriction defines a proper vertex coloring?

Practice 6: Complete Graph

Find

Practice 7: Even Cycle

Find

Practice 8: Odd Cycle

Find

Practice 9: Bipartite Graph

A connected graph with at least one edge is bipartite.

What is its chromatic number?

Practice 10: Identify the Error

A student says, “This drawing has two crossing edges, so the graph is nonplanar.”

Explain the error.

Practice Answers

Practice 1

A planar graph must have at least one drawing in the plane in which edges meet only at common endpoints.

Practice 2

Use

Then

so

Practice 3

For \(V=7\),

Since

the graph cannot be planar.

Practice 4

For \(K_5\),

But

Since \(10>9\),

Practice 5

Adjacent vertices must receive different colors:

Practice 6

Every pair of vertices in \(K_6\) is adjacent, so all six vertices require different colors:

Practice 7

An even cycle is bipartite:

Practice 8

An odd cycle cannot be two-colored but can be three-colored:

Practice 9

A connected bipartite graph with at least one edge requires exactly two colors:

Practice 10

A crossing in one particular drawing does not prove that every drawing must contain a crossing.

The graph may be redrawable without crossings.

What to Remember

• A planar graph can be drawn in the plane without edge crossings.
• A plane graph is one specific crossing-free embedding.
• For a connected plane graph, \(V-E+F=2\).
• For a simple planar graph with \(V\ge3\), \(E\le3V-6\).
• For a simple bipartite planar graph with \(V\ge3\), \(E\le2V-4\).
• \(K_5\) and \(K_{3,3}\) are fundamental nonplanar graphs.
• A proper vertex coloring assigns different colors to adjacent vertices.
• The chromatic number is the minimum number of colors required.
• Bipartite graphs are exactly the graphs that can be colored with at most two colors.
• Every planar graph can be colored with at most four colors.

Where We Go Next

Planarity constrains how a graph can be embedded, while coloring constrains how adjacent objects can be distinguished. The next problems return to weighted networks and ask how to move through them efficiently.

The next lesson, Shortest Paths, develops methods for finding minimum-cost routes between vertices in weighted graphs.