CG11 Which Graphs are Planar?

How do we prove that K_5 or K_{3,3} are not planar graphs? Using Euler's formula for planar graphs, we prove a necessary condition that puts restriction on the number of edges of a planar graph (based on the number of vertices & the girth of the graph). Will also introduce subdivisions and Kuratowski's theorem that gives a necessary & sufficient condition for planarity. Subscribe @Shahriari for in depth math videos for undergraduates.
00:00 Introduction
00:17 Outline
02:54 Example: Is this graph planar?
03:54 What about K_{3,3} or K_5
06:12 Main Theorem: An upper bound for # of edges of a connected planar simple graph
07:24 For a connected planar simple graph # of edges no more than 3v-6
07:47 If also triangle-less then e no more than 2v-4
08:18 Proof: K_5 not planar
08:48 Proof: K_{3,3} not planar
09:32 Proof: Petersen graph is not planar
10:30 Proof of Main Theorem
12:24 Definition: Subdivisions
13:15 Subdivisions and Subgraphs of Planar graphs
14:31 Example using subgraphs & subdivisions to prove non-planarity
17:16 Kuratowski's Theorem
18:08 Videos on Planarity

Shahriar Shahriari is the William Polk Russell Professor of Mathematics at Pomona College in Claremont, CA USA