There are $n > 2022$ cities in the country. Some pairs of cities are connected with straight two-ways airlines. Call the set of the cities {\it unlucky}, if it is impossible to color the airlines between them in two colors without monochromatic triangle (i.e. three cities $A$, $B$, $C$ with the airlines $AB$, $AC$ and $BC$ of the same color). The set containing all the cities is unlucky. Is there always an unlucky set containing exactly 2022 cities?
Problem
Source: VII Caucasus Mathematical Olympiad
Tags: combinatorics, graph theory
shinhue
20.01.2023 01:43
bump this gem
matinyousefi
24.08.2023 16:45
The answer is negative. We will construct a graph with 2023 vertices such that the whole graph is unlucky but every 2020 subgraph is not so. Note that if we add some empty vertices to the graph a counterexample for all $n$ is built. Observation 1. If we color $K_5$ properly every vertex has 2 edges of each color; otherwise 3 edges have same color and the triangle forming by their uncommon vertices cannot be colored properly.
Take a vertex $v_1$ and let it connect with color blue to $v_2, v_3$ and color red to $v_4, v_5$. $v_4v_5$ must be blue and $v_2v_3$ must be red. WLOG assume that $v_2v_4$ is red, then $v_3v_4$ must be blue, so $v_3v_5$ must be red and $v_2v_5$ must be blue.
This is because every one of four vertices due to observation 1 misses an specific color to be complete and hence the edges of any vertex connecting to these four has a unique way of coloring.
It is now enough to make a cycle of $K_5$s. Put 2023 vertices on a circle and connect each vertex to all 4 nearest points in each direction. Assume for the sake of contradiction that the said graph could be properly colored. Then consider 5 consecutive points on the circle. They form a $K_5$. Now the next 5 points on the circle form a $K_5$ that only differs in one vertex and due to observation 3 must be colored with the same pattern. We can conclude that the edges that connect two consecutive points is colored in a repeating pattern of length 5. But 2023 is not divisible by 5 and hence such pattern cannot exist. The contradiction means the said graph with $2023$ vertices cannot be properly colored. Meanwhile every subgraph of size 2022 can be colored properly. We only need to color a $K_5$ and just as described color other $K_5$s one by one in each direction.
Sticking to $K_5$ came to mind after noting that $R(3,3) = 6$ and so every $K_6$ cannot be properly colored, this suggest that a weak $K_6$ could be bound to some restriction. After noting that $K_5$ is restricted, working with a cycle to abuse the restriction is quite natural.