Lesson 3

Theorem. Graphs \(K_{5}\) and \(K_{3,3}\) are not planar.

Proof. The non-planarity of \(K_{5}\) follows directly from the inequality \(|E| \le 3|V|-6\): \[|E(K_{5})|=10 \not \leq 9=15-6=3|V(K_{5})|-6 \ .\] But the non-planarity of \(K_{3,3}\) does not follow: \[|E(K_{3,3})|=9 \leq 12=18-6=3|V(K_{3,3})|-6 \ .\] To prove non-planarity, we need a stronger inequality, recalling that in a bipartite graph, there are no odd-length cycles. Thus, each face is bounded by at least four edges and \(4|F| \le 2|E|\). Then, \[|V|-2=|E|-|F| \ge |E|/2 \ .\] And with this inequality, a contradiction arises: \[|V(K_{3,3})|-2=4 \not \ge 4.5 = |E(K_{3,3})|/2 \ .\]◼