Track / Stage 5 / 310 of 400 #910 of 1964

Problem 910

AIME late

Combinatorics Difficulty 5.7 Prove it

Let $\mathcal{G}$ be a planar graph with a finite number of vertices. Show that there exists a point in $\mathcal{G}$ with a degree not exceeding 5.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Each face of the graph has at least 3 sides, and each edge is on two faces, so $2 A \geq 3 F$ . By Euler's formula,

$F+S=A+2, \Longrightarrow S \geq A+2-\frac{2}{3} A=\frac{1}{3} A+2$

Now suppose that all vertices have degree $\geq 6$ . Then

$2 A=\sum d(x) \geq 6 S$

It is easy to see that these two inequalities are contradictory.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.