Graph Theory 4: Non-Planar Graphs & Kuratowski's Theorem

Summary

This video explores key concepts in graph theory, focusing on planar and non-planar graphs. It introduces K4, K5, and K33, explaining how K4 can be drawn without edge crossings, while K5 and K33 cannot be. The Curtis-Kleis Theorem from 1930 is highlighted, showing that non-planar graphs contain subgraphs homeomorphic to K5 or K33. The Peterson graph is used as an example to demonstrate this theorem in action. The video explains the process of homeomorphism, where vertices of degree 2 can be removed to reveal the non-planar nature of a graph. Overall, it provides a thorough understanding of graph planarity and non-planarity.

Takeaways

• 😀 K4 is the complete graph on four vertices where each vertex is connected to every other vertex by an edge.
• 😀 K4 can be drawn in a planar way, where no edges cross, meaning it is a planar graph.
• 😀 K5, the complete graph on five vertices, cannot be drawn without edge intersections, making it a non-planar graph.
• 😀 K5 is an example of a non-planar graph because no matter how it is drawn, the edges will always cross each other.
• 😀 K33 is another non-planar graph where six vertices are partitioned into two sets of three, and all vertices in one set connect to all vertices in the other set.
• 😀 K33, like K5, cannot be drawn in a way that avoids edge intersections, making it another example of a non-planar graph.
• 😀 Kuratowski's theorem (1930) shows that K5 and K33 are the canonical examples of non-planar graphs.
• 😀 Every non-planar graph contains a subgraph that is homeomorphic to either K5 or K33.
• 😀 A homeomorphism in graph theory means that if vertices of degree 2 are removed, the graph can be transformed into either K5 or K33.
• 😀 The Peterson graph is non-planar and contains a subgraph homeomorphic to K33, demonstrating the concept of non-planarity and homeomorphism in graph theory.

Q & A

What is a complete graph in graph theory?

A complete graph is a type of graph where every pair of vertices is connected by exactly one edge. For example, K4 is a complete graph on four vertices, and K5 is a complete graph on five vertices.

What does it mean for a graph to be planar?

A graph is planar if it can be drawn in a plane without any of its edges crossing each other. If it is impossible to draw the graph without edge intersections, the graph is non-planar.

Can K4, the complete graph on four vertices, be drawn without edges crossing?

Yes, K4 can be drawn without any edges crossing, making it a planar graph.

Is it possible to draw K5, the complete graph on five vertices, without edge crossings?

No, K5 is a non-planar graph, and it is impossible to draw it without some of the edges crossing.

What is K33 and why is it considered non-planar?

K33 is a complete bipartite graph where six vertices are divided into two sets of three, with every vertex in one set connected to all vertices in the other set. It is non-planar because no matter how you arrange the vertices and edges, they will always intersect.

What is Curtis Keys' theorem and why is it important in graph theory?

Curtis Keys' theorem, proven in 1930, states that every non-planar graph contains a subgraph that is homeomorphic to either K5 or K33. This theorem helps identify non-planar graphs by recognizing these two canonical non-planar graphs within them.

What does 'homeomorphic' mean in the context of graph theory?

In graph theory, 'homeomorphic' means that two graphs can be transformed into each other by removing or adding vertices of degree 2. Essentially, if a graph can be simplified to another by this process, the graphs are homeomorphic.

How does homeomorphism help in identifying non-planarity in graphs?

Homeomorphism allows us to simplify complex graphs by removing degree 2 vertices and replacing them with a single edge. If the resulting graph is homeomorphic to K5 or K33, it indicates that the original graph is non-planar.

What is the Peterson graph, and how is it related to non-planarity?

The Peterson graph is a well-known graph in graph theory consisting of 10 vertices and 15 edges. It is non-planar, and by removing certain vertices and edges, it contains a subgraph that is homeomorphic to K33, demonstrating its non-planarity.

How can the Peterson graph be simplified to show its non-planarity?

By removing certain vertices and edges from the Peterson graph, we can obtain a subgraph that is homeomorphic to K33. This simplification proves that the Peterson graph is non-planar because it contains a subgraph that is non-planar itself.