Graph Theory: 61. Characterization of Planar Graphs

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 - • Graph Theory: 60. Non ...
GT59 Maximal Planar Graphs - • Graph Theory: 59. Maxi...
GT58 Euler's Formula for Plane Graphs - • Graph Theory: 58. Eule...
GT57 Planar Graphs - • Graph Theory: 57. Plan...
For quick videos about Math tips and useful facts, check out my other channel
"Spoonful of Maths" - / spoonfulofmaths
Video Production by: Giuseppe Geracitano (goo.gl/O8TURb)