Petersen graph is not planar

Task number: 4243

Prove in two ways that the Petersen graph is not planar.

Petersen graph
  • Solution

    The first way: by using the Kuratowski’s theorem, because it contains a subdivision of \( K_ {3{,}3} \)

    Subdivision of K_33

    The second way: the contractions maintain planarity, but by the contraction of the matching between the outer and inner five-cycle we get a non-planar graph \( K_5 \).

    Third way: Petersen’s graph has no triangles or fourcycles. If it was planar, it should, as a consequence of Euler’s formula, satisfy the estimate \( | E_P | \le \frac53 (| V_P | -2) \), which it does not satisfy.

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