Looking for a 4-cycle in a graph
Source: Bundeswettbewerb Mathematik 2021, Round 2 - Problem 2
September 22, 2021
combinatoricscombinatorics proposedgraph theorygraph cycles
Problem Statement
A school has 2021 students, each of which knows at least 45 of the other students (where "knowing" is mutual).Show that there are four students who can be seated at a round table such that each of them knows both of her neighbours.