Prove that Petersen's graph is non-planar using Euler's formula

Question

Prove that Petersen's graph is non-planar using Euler's formula. I know that $n - m + f = 2$. But should I count $f$ and prove that the summation does not equal to two or solve to get $f =7$ and argue that it is impossible???

Answer 1

Using your notation, we have that $n=10$, $m=15$. Inspecting the graph, we see that (1) each edge is included in exactly two faces, and (2) each cycle has a length of 5 or greater. Combining these two facts yields $5f \le 2m.$ Substituting this into Euler's formula, we obtain a contradiction.

Answer 2

If you can use the definition of planar graph, you can "contract" edges just to get $ K_5 $ or $ K_{3,3} $ and there you prooved that Petersen's graph is non-planar.

Answer 3

We know the Petersen graph has $15$ edges and $10$ vertices. In a planar graph, $V+F-E=2$. In Petersen, that would be $10+F-15 = 2$, so it would have $7$ faces in it's planar embedding. The minimal cycle in Petersen is $5$, so it would need to be made from pentagons, hexagons, or larger.

$7$ pentagons = $35$ edges or more. Half that, rounded down = $17$ edges. Each edge can only be used twice, and we've gone over.