📂Graph Theory

Planar Graphs and Kuratowski's Theorem

Definition

Planar Graph

A planar graph is a graph that can be drawn on a plane without any edges crossing each other.

Explanation

When a planar graph is drawn, the regions that are demarcated on the plane are called faces. The following planar graph $K_{4}$ has four faces $f_{1}, f_{2}, f_{3}, f_{4}$, and among them, the one that is not bounded $f_{4}$ is called an infinite face.

Planar Graphs, as the name suggests, refer to graphs that can be drawn on a plane without any overlapping parts. To understand them better, it’s more helpful to see what non-planar graphs look like. For instance, the complete graph $K_{5}$ and the bipartite graph $K_{3,3}$ are not planar because, no matter how you try, there will be crossing edges.

Naturally, mathematicians would be curious about the conditions that make a graph planar. Regarding this, a generalized theorem is known for the example above.

Theorem

Kuratowski’s Theorem ¹

A graph is planar if and only if none of its subgraphs is homeomorphic to $K_{5}$ or $K_{3,3}$.

Significance

Simply put, this theorem guarantees that if something similar to $K_{5}$ or $K_{3,3}$ is included, the graph is not planar, and if these are absent, then it is planar. At first glance, it might seem that this theorem makes everything about planar graphs clear, but graph theory has spawned a vast array of concepts and problems rooted in planar graphs. Starting with the simplest generalization that allows $k \in \mathbb{N}$ edges to overlap, it extends to commonly encountered disciplines in mathematics like duality, argumentative geometry dealing with dots, lines, and surfaces, and even combinatorial topology, which is interested in the structure of space itself, marking the beginning of a monumental journey.

Thus, while it’s not said that those who aren’t majoring in graphs necessarily need to be familiar with various theorems about planar graphs and skilled in proving them, it’s certainly a concept worth knowing to understand the broader world of mathematics. As definitions go, you don’t need a vast mathematical background to understand planar graphs in the first place. Just, let’s at least know about it.

Autism Test

One of the older internet memes, this problem is called the Autism Test. The problem sets a constraint that water, electricity, and gas must be supplied to three houses without the lines crossing and claims “it’s difficult but possible.” If we look at this purely as a mathematical problem, we can argue that it’s impossible based on Kuratowski’s Theorem. The reason these memes are called ‘Autism Tests’ is perhaps because they’re a sort of contemptuous, derogatory joke, suggesting that ‘insisting on solving something impossible and trying to consider all possibilities looks similar to autism.’

Approaching it non-mathematically, there exists a solution like the one above. In fact, the wholesome fun of the autism test lies in such forced or ingenious cheats that break the conditions of the problem.