Kuratowski’s Theorem in Discrete Mathematics

Kuratowski established the theorem establishing a necessary and sufficient condition for planarity in 1930. The theorem states that –

"If G is non planar if and only if G contains a sub-graph that is a subdivision
 of either K3,3 or K5."

Kuratowski’s Theorem Definition

Kuratowski’s Theorem characterizes planar graphs. It states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of either K₅​ (complete graph on five vertices) or K_3,3​ (complete bipartite graph on six vertices, three of which connect to each of the other three).

To prove this theorem, we’ll go through some definitions and make sure that both K3,3 and K5 are non-planar. Let’s have a look at K_3,3. 

Proposition 1  – K_3,3 is not planar.

Proof:

Now, we will prove it by contradiction.  
Say, to the contrary, that K_3,3 is planar.  Then there is a plane embedding of K_3,3 satisfying :
Then, by Euler’s Formula : v − e + f = 2, where  v = total vertices, e = no of edges , f = total faces.
 

In figure (a), the bi-partite graph : v= 6 and e= 9. 

As K_3,3 is bipartite, there are no 3-cycles in it(odd cycles can be there in it).  
So, each face of the embedding must be bounded by at least 4 edges from K_3,3. 
Moreover, each edge is counted twice among the boundaries for faces.  
Hence, we must have :  f ≤2 *e/4 
⇒ f ≤ e/2  
⇒ f ≤ 4.5.
Now put this data in the Euler’s formula :we get : 2 =v−e+f
⇒ 2 ≤ 6−9 + 4.5 
⇒ 2 ≤ 1.5, which is obviously false.  
So, we can say that  K_3,3 is a non-planar graph.

Proposition 2 – K5 is not planar.

Proof:

Every planar graph must follow  : e ≤ 3v − 6 (corollary of Euler’s formula)
For graph (b) in the above diagram, e = 10 and v = 5. 
LHS : e = 10
RHS : 3*v – 6 = 15 – 6 = 9
⇒ 10 ≤ 9, which is not true.
So, we can say that  K₅ is a non-planar graph.

Example – Kuratowski’s Theorem

1. Prove that : A planar graph’s sub-graphs are all planar.

Proof:

Let G be the graph & P be its sub-graph.
There exists a planar embedding of G, if G is planar. In the planar embedding of G, we can locate the vertices and edges of every sub-graph P of G.
This is how a planar embedding of P is created.

2. A non-planar graph’s subdivisions are all non-planar.

Proof:

Assume that for G, a planar embedding of its subdivision, P, exists. 
We acquire a planar embedding of G and find G planar when we remove the vertices formed in edge-subdivisions and reconstruct the original edge (without affecting the shape and position of the path).
As a result, if G is non-planar, so is every subdivision (P) of G.

The Four Color Theorem and Kuratowski’s Theorem are two fundamental results in discrete mathematics, specifically in the field of graph theory. Both theorems address the properties of planar graphs but from different perspectives.

In this article, we will understand about Four Color Theorem and Kuratowski’s Theorem in Discrete Mathematics, their definition, examples, and semantic differences between them.