Found problems: 7
2021 Bundeswettbewerb Mathematik, 2
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.
2023 China National Olympiad, 6
There are $n(n\ge 8)$ airports, some of which have one-way direct routes between them. For any two airports $a$ and $b$, there is at most one one-way direct route from $a$ to $b$ (there may be both one-way direct routes from $a$ to $b$ and from $b$ to $a$). For any set $A$ composed of airports $(1\le | A| \le n-1)$, there are at least $4\cdot \min \{|A|,n-|A| \}$ one-way direct routes from the airport in $A$ to the airport not in $A$.
Prove that: For any airport $x$, we can start from $x$ and return to the airport by no more than $\sqrt{2n}$ one-way direct routes.
2019 Canada National Olympiad, 5
A 2-player game is played on $n\geq 3$ points, where no 3 points are collinear. Each move consists of selecting 2 of the points and drawing a new line segment connecting them. The first player to draw a line segment that creates an odd cycle loses. (An odd cycle must have all its vertices among the $n$ points from the start, so the vertices of the cycle cannot be the intersections of the lines drawn.) Find all $n$ such that the player to move first wins.
2019 Iran RMM TST, 5
Edges of a planar graph $G$ are colored either with blue or red. Prove that there is a vertex like $v$ such that when we go around $v$ through a complete cycle, edges with the endpoint at $v$ change their color at most two times.
Clarifications for complete cycle:
If all the edges with one endpoint at $v$ are $(v,u_1),(v,u_2),\ldots,(v,u_k)$ such that $u_1,u_2,\ldots,u_k$ are clockwise with respect to $v$ then in the sequence of $(v,u_1),(v,u_2),\ldots,(v,u_k),(v,u_1)$ there are at most two $j$ such that colours of $(v,u_j),(v,u_{j+1})$ ($j \mod k$) differ.
2013 Danube Mathematical Competition, 3
Show that, for every integer $r \ge 2$, there exists an $r$-chromatic simple graph (no loops, nor multiple edges) which has no cycle of less than $6$ edges
2023 China MO, 6
There are $n(n\ge 8)$ airports, some of which have one-way direct routes between them. For any two airports $a$ and $b$, there is at most one one-way direct route from $a$ to $b$ (there may be both one-way direct routes from $a$ to $b$ and from $b$ to $a$). For any set $A$ composed of airports $(1\le | A| \le n-1)$, there are at least $4\cdot \min \{|A|,n-|A| \}$ one-way direct routes from the airport in $A$ to the airport not in $A$.
Prove that: For any airport $x$, we can start from $x$ and return to the airport by no more than $\sqrt{2n}$ one-way direct routes.
2020 USA EGMO Team Selection Test, 5
Let $G = (V, E)$ be a finite simple graph on $n$ vertices. An edge $e$ of $G$ is called a [i]bottleneck[/i] if one can partition $V$ into two disjoint sets $A$ and $B$ such that
[list]
[*] at most $100$ edges of $G$ have one endpoint in $A$ and one endpoint in $B$; and
[*] the edge $e$ is one such edge (meaning the edge $e$ also has one endpoint in $A$ and one endpoint in $B$).
[/list]
Prove that at most $100n$ edges of $G$ are bottlenecks.
[i]Proposed by Yang Liu[/i]