Graph Theory: 60. Non Planar Graphs

In this video we formally prove that the complete graph on 5 vertices is non-planar. Then we prove that a planar graph with no triangles has at most 2n-4 edges, where n is the number of vertices. Using this fact, we formally prove that the complete biparite graph with partite sets both of size 3 is non-planar.
-- Bits of Graph Theory by Dr. Sarada Herke.
Related videos:
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...
GT19 Graph is Bipartite iff No Odd Cycle - • Graph Theory: 19. Grap...
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)