### Graph Theory – Proofs that K5 and K3,3 are not planar

```Graph Theory –
Proofs that K5 and K3,3
are not planar
www.waldomaths.com
The Proofs that K5 and K3,3 are not planar
K5
Complete graph with 5 nodes
K3,3
Complete bipartite graph
with 3 + 3 nodes
Proof that K5 is not planar
Assume K5 is planar
----------------------
So K5 is not planar
Proof that K5 is not planar
Assume K5 is planar
Then it obeys Euler’s Relationship
R+N=A+2
N=5
A = 10
so R = 7
Each region is bounded by at least three arcs
So there are at least 3R region boundaries
So there are at least 3R ÷ 2 arcs, since each
arc is 2 region boundaries
3 × 7 ÷ 2 = 10.5, so at least 11 arcs
But there are 10 arcs
So K5 doesn’t obey Euler’s Relationship.
So K5 is not planar
QED
Proof that K3,3 is not planar
Assume K3,3 is planar
Then it obeys Euler’s Relationship
R+N=A+2
N=6
A=9
so R = 5
Each region is bounded by at least four arcs
So there are at least 4R region boundaries
So there are at least 4R ÷ 2 or 2R arcs, since
each arc is 2 region boundaries
2 × 5 = 10, so at least 10 arcs
But there are 9 arcs