Vertices of degree at most 11
Task number: 4515
Prove that in a planar graph, at least half of the vertices have degree at most 11.
Solution
For graphs on at most 2 vertices the statement obviously holds.
Assume for a contradiction, that there exists a graph on \(n\ge 3\) vertices in which at least half of the vertices are of degree at least 12. Then the sum of all degrees is at least \(12\cdot (n/2)=6n\). Thus, there are at least \(3n\) edges in the graph, which contradicts with the upper bound of \(3n-6\) for the number of edges of a planar graph on at least 3 vertices.
