Nonplanarity of a complete graph
Task number: 4244
Without using the Kuratowski’s theorem, prove that the graph \( K_5 \) is not planar.
Hint
How many edges may a planar graph have?
Solution
A planar graph on \( n \) vertices may have at most \( 3n-6 \) edges. With five vertices, therefore, no more than nine edges. In contrary, the complete graph \( K_5 \) has \( 10 \) edges.
