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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email