MathDB

3

Part of 2022 Polish MO Finals

Problems(1)

Pruning a highly connected graph

Source: Poland 73-3-3

3/31/2022
One has marked nn points on a circle and has drawn a certain number of chords whose endpoints are the marked points. It turned out that the following property is satisfied: whenever any 20212021 drawn chords are removed one can join any two marked points by a broken line composed of some of the remaining drawn chords. Prove that one can remove some of the drawn chords so that at most 2022n2022n chords remain and the property described above is preserved.
combinatorics