Task list filter?
Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.
Task rankings
Difficulty level
Task tags
Task type
«
«
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≥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⋅(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.
