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
«
«
Independent set
Task number: 4217
Prove that each tree on n vertices has an independent set of size at least ⌈n2⌉.
Solution
Each tree is bipartite, so it can be colored with two colors. Each color class specifies an independent set. One of these two classes contains at least half of the vertices.