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 Planar Graphs  
GT59 Maximal Planar Graphs -    • Graph Theory: 59. Maximal Planar Graphs  
GT58 Euler's Formula for Plane Graphs -    • Graph Theory: 58. Euler's Formula for...  
GT57 Planar Graphs -    • Graph Theory: 57. Planar Graphs  


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)