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 n3 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 3n6 for the number of edges of a planar graph on at least 3 vertices.

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email