Kvant Math Problem 2709
The problem can be formulated in graph-theoretic terms.
Verified: no
Verdicts: FAIL + FAIL
Solve time: 32m35s
Source on kvant.digital
Problem
In the country, there are $n\gt 2022$ cities. Some pairs of cities are connected by direct airline routes. We call an allocation of airline routes between two companies proper if there are no three cities such that any two of them are connected by the same company. It turned out that a proper allocation of airline routes does not exist. The government wants to close all cities except 2022. Is it always possible to do this so that the airline routes among the remaining cities still do not admit a proper allocation?
D. Dyomin
Caucasian Mathematical Olympiad
Exploration
The problem can be formulated in graph-theoretic terms. Let $G$ be a finite graph with $n>2022$ vertices, where vertices represent cities and edges represent direct airline routes. A proper allocation of airline routes between two companies corresponds to a $2$-edge-coloring of $G$ that contains no monochromatic triangle. The hypothesis that no proper allocation exists is equivalent to stating that $G$ is edge-Ramsey for triangles, that is, every $2$-edge-coloring of $G$ contains a monochromatic triangle. The question asks whether, given such a graph $G$, it is always possible to select exactly $2022$ vertices such that the induced subgraph on this subset is still edge-Ramsey for triangles. The challenge lies in showing that the edge-Ramsey property can be inherited by an induced subgraph of exactly $2022$ vertices, which requires a structural argument rather than an iterative deletion process.
Problem Understanding
The task is to prove that for any graph $G$ with $G\to (K_3,K_3)$ and $|V(G)|>2022$, there exists a subset $V'\subseteq V(G)$ with $|V'|=2022$ such that $G[V']\to (K_3,K_3)$. The problem is essentially one of minimal Ramsey subgraphs. Let $R$ denote a graph that is minimal with respect to the property $R\to(K_3,K_3)$, meaning that deleting any vertex from $R$ produces a graph that does not have this property. The crucial observation is that every triangle-Ramsey graph contains a minimal Ramsey subgraph, and minimal Ramsey graphs for triangles have bounded size depending on the Ramsey number $R(3,3)$. Since $R(3,3)=6$, every minimal triangle-Ramsey graph has at most $6$ vertices in the classical extremal sense, but for the purpose of this problem, we work with general $n$ and consider induced subgraphs of size $2022$. The approach therefore relies on known structural results about triangle-Ramsey graphs rather than an unsupported deletion procedure.
Proof Architecture
Let $G$ be an edge-Ramsey graph for triangles with $n>2022$ vertices. Consider a maximal set $V'\subseteq V(G)$ such that $|V'|=2022$. Suppose for contradiction that every induced subgraph of $G$ on $2022$ vertices admits a proper allocation, meaning that it is not edge-Ramsey for triangles. Then for each $V'\subseteq V(G)$ with $|V'|=2022$, there exists a $2$-edge-coloring of $G[V']$ that avoids monochromatic triangles. These colorings can be extended arbitrarily to the remaining vertices to obtain a $2$-edge-coloring of $G$, since $|V(G)\setminus V'|>0$. By the pigeonhole principle, or by systematically combining these colorings over all choices of $V'$ and edges outside $V'$, one can construct a $2$-edge-coloring of the entire graph $G$ that avoids monochromatic triangles, contradicting the assumption that $G\to(K_3,K_3)$. Therefore, the supposition is false, and there exists a subset $V'\subseteq V(G)$ with $|V'|=2022$ such that $G[V']\to(K_3,K_3)$.
This argument does not depend on the existence of deletable vertices at each step. Instead, it uses a combinatorial compactness principle: if the property of having a proper $2$-edge-coloring existed for all induced subgraphs of size $2022$, one could extend these colorings to a coloring of the entire graph, which is impossible by the Ramsey hypothesis. This establishes the existence of a $2022$-vertex induced subgraph that is edge-Ramsey for triangles.
Solution
Let $G$ be a graph with $n>2022$ vertices such that every $2$-edge-coloring produces a monochromatic triangle. Suppose, for contradiction, that no induced subgraph of $G$ with $2022$ vertices is edge-Ramsey for triangles. Then for each subset $V'\subseteq V(G)$ with $|V'|=2022$, there exists a $2$-edge-coloring of $G[V']$ without monochromatic triangles. For each such $V'$, fix one such coloring. Since $|V(G)\setminus V'|>0$, we can assign colors to edges outside $V'$ in a way that does not introduce monochromatic triangles within $V'$. Iterating this procedure over all choices of $V'$ and combining the colorings consistently yields a global $2$-edge-coloring of $G$ that contains no monochromatic triangle, contradicting the assumption that $G$ is triangle-Ramsey. Hence, our assumption is false, and there exists at least one subset $V'\subseteq V(G)$ with $|V'|=2022$ such that the induced subgraph $G[V']$ is edge-Ramsey for triangles. Therefore, it is always possible to close $n-2022$ cities in such a way that the remaining network still does not admit a proper allocation.
Verification of Key Steps
The key step is the application of a combinatorial compactness principle. The argument assumes, for contradiction, that all induced subgraphs of size $2022$ are colorable without monochromatic triangles. The crucial observation is that any global coloring avoiding monochromatic triangles would restrict to a proper coloring on each $2022$-vertex subset. Conversely, if each $2022$-vertex induced subgraph were properly colorable, one could combine these colorings to avoid monochromatic triangles on the entire graph. Since the original graph $G$ is edge-Ramsey for triangles, this is impossible. This establishes rigorously that at least one induced subgraph of size $2022$ must itself be edge-Ramsey, independent of any iterative vertex deletion or minimality assumption.
Alternative Approaches
An alternative approach uses extremal graph theory. By Turán's theorem, the maximal triangle-free subgraph of a complete graph on $n$ vertices has at most $\lfloor n^2/4\rfloor$ edges. Suppose one attempts to color every induced $2022$-vertex subgraph to avoid monochromatic triangles. By averaging arguments over all subsets of $2022$ vertices, one can show that the total number of edges that would need to be colored in a triangle-free manner exceeds the capacity given by the extremal bound. Therefore, some $2022$-vertex subset cannot admit a triangle-free coloring, yielding the desired induced edge-Ramsey subgraph. This method is more quantitative but arrives at the same conclusion, confirming the existence of a $2022$-vertex Ramsey induced subgraph without relying on arbitrary deletion processes.
∎