We have seen in a previous video that K5 and K3,3 are non-planar. In this video we define an elementary subdivision of a graph, as well as a subdivision of a graph. We then discuss the fact that if a graph G contains a subgraph which is a subdivision of a non-planar graph, then G is non-planar. The remarkable thing is that Kuratowski's Theorem says that the graphs containing subgraphs which are subdivisions of either K5 or K3,3 are the ONLY graphs which are non-planar. In otherwords, the characterization of planar graphs is: A graph G is planar if and only if it contains no subgraph which is a subdivision of either K5 or K3,3. The proof of Kuratowski's Theorem is very long and detailed, and is omitted here.
-- Bits of Graph Theory by Dr. Sarada Herke.
Related videos:
GT60 Non-Planar Graphs - [ Ссылка ]
GT59 Maximal Planar Graphs - [ Ссылка ]
GT58 Euler's Formula for Plane Graphs - [ Ссылка ]
GT57 Planar Graphs - [ Ссылка ]
For quick videos about Math tips and useful facts, check out my other channel
"Spoonful of Maths" - [ Ссылка ]
Video Production by: Giuseppe Geracitano (goo.gl/O8TURb)
