
Proof that every finite planar graph contains at least
one vertex with valence less than six
Assume, to the contrary, that
there is a finite planar graph with all vertices having valence
>= 6. (1)
Let V,E,F be the number of vertices, edges, faces respectively.
Then 2*E = SUM(vertices v) valence of v
>= SUM(vertices
v) 6 since
each valence >= 6 by (1)
= 6*V
I.e. V <= E/3
(2)
Also, 2*E = SUM(faces f) valence of f
>= SUM(faces f)
3 (equality if the graph is triangulated)
= 3*F
I.e. F <= 2*E/3
(3)
Euler's formula says:
2 = V  E + F
<= E/3  E +
2*E/3
by (2) and (3)
= 0
Contradiction.