📂Graph Theory

Definition of Maps in Graph Theory

Definition ¹

1. A planar graph connected by $3$ is defined as a map.
2. A map that can be colored with $k$ different colors in such a way that adjacent faces across the same edge have different colors is called a $k$-face colorable map.
3. The existing $k$-colorable graph is called a $k$-vertex colorable graph.

---

• The regions distinguished on the plane while drawing a planar graph are called faces.

Description

1. $3$-Graph is a constraint intended to exclude cases that cannot be called maps, and it’s a very good definition for being short and clear. The following are examples of graphs disconnected by $1$ and $2$ vertices, respectively, which are unrealistic in actual maps. In the left case, the removal of one red vertex creates a disconnected graph due to an unrealistic edge, and in the right case, removal of the red vertices on both sides creates a disconnected graph due to an unrealistic vertex.

2. How many different colors are needed to distinguish each area, or face, of such a map with different colors? The number of colors seems to increase as the map becomes more complex, but not as many as one might think since only adjacent areas need to differ. For example, the following is the world map colored with just $4$ colors. Such a question can be abstracted into a mathematical concept called $k$-face coloring. This is a typical combinatorial style problem, asking not just about the world map but whether all possible maps can be differentiated with $4$ colors, which is the $4$ color problem.

3. Vertex coloring is simply a term used to distinguish from face coloring of maps. The $4$ color problem can be solved as a problem of graph theory through the following theorem.

Theorem

If $G$ is a simple connected planar graph, and $G^{ \ast }$ is its geometric dual, then the following hold: $G$ is $k$-vertex colorable, $G^{ \ast }$ is $k$-face colorable

Proof

Strategy: There’s really no “proof” to speak of, as the result is naturally obtained from the concept of the dual graph.

---

$(\Rightarrow)$

Since $G$ is a simple connected graph, $G^{ \ast }$ is a map. If $G$ has a $k$-coloring for vertices, then the faces $f^{ \ast }$ corresponding to each $v \in V(G)$ in $G^{ \ast }$ can be given the exact same $k$-coloring. As adjacent vertices in $G$ were colored differently according to the assumption, adjacent faces in $G^{ \ast }$ are also colored differently. Therefore, $G^{ \ast }$ is $k$-face colorable.

---

$(\Leftarrow)$

The proof of the converse is essentially no different.

■