Abstract Kuratowski's Theorem (Theorem 7.6.1)
A graph is planar if and only if it does not contain an edge subdivision of or as a subgraph.
The proof for this is seen in CO342.
This theorem is used to prove that a graph is non-planar.
You cannot repeat edges when you try to find the edge subdivision.
To convince yourself: Else, About a planar graph that looks similar to , with one vertex in the center. If you can repeat vertices, you would easily be able to build , and come to a contradiction.
At first, I was really struggling, but it just comes down to 2 steps:
- Selecting your bipartition of vertices, and alternate.
- Then, color in your edges. It just works oftentimes