Ukrainian Mathematical Olympiad

Let $G$ be the graph of the problem. Partition the set $V_G$ of its 2012 vertices into three subsets $A$, $B$, and $C$ so that the sum $S$ of the numbers of edges in the subgraphs $G(A)$, $G(B)$, and $G(C)$ is minimal (clearly, this is possible). Suppose that in one of the subsets (let it be $A$), there is a vertex $X$ such that in the subgraph $G(A)$ its degree ${\rho }_{G(A)}(X)\ge 3$. Since ${\rho }_G(X)\le 8$, the vertex $X$ cannot be connected to each of the subgraphs $G(B)$ and $G(C)$ by more than two edges. Suppose the vertex $X$ is connected to the subgraph $G(B)$ by at most two edges. Then, for the subgraphs $G(A\setminus \{X\})$, $G(B\cup \{X\})$, and $G(C)$, the sum $S$ decreases, which is impossible. Therefore, in the subgraphs $G(A)$, $G(B)$, and $G(C)$, the degree of all their vertices does not exceed 2. As is known, in any graph, the sum of the degrees of all vertices equals twice the number of edges, so in each of the subgraphs $G(A)$, $G(B)$, and $G(C)$, the number of edges does not exceed the number of vertices, that is, $S\le 2012$. Remove all these $S$ edges (make the graphs with vertex sets $A$, $B$, and $C$ empty). For any four vertices, at least two lie in one of these three vertex sets, and after removing the edges, such two vertices are not connected by an edge.

Solution 2:

Let us prove the following auxiliary fact.

Lemma. If in a graph $G$ with $n$ vertices the degree of each vertex does not exceed $p$, then all its vertices can be partitioned into $q\le p+1$ groups so that in each group no two vertices are connected by an edge.

Proof. We use induction on the order $n$ of the graph. The base case is obvious. Suppose the statement holds for $n=k$. Consider a graph $G$ with $k+1$ vertices that satisfies the lemma's condition. Let $X$ be any of its vertices. For the subgraph $G(V_G\setminus \{X\})$, we can apply the induction hypothesis and partition the set $V_G\setminus \{X\}$ of all its vertices as required into $q\le p+1$ groups. Since ${\rho }_G(X)\le p$, the vertex $X$ is not connected by any edge to at least one of the formed groups. It remains to add $X$ to this group, and the lemma is proved. $\square$



Partition — according to the lemma — the set of vertices of the graph $G$ of the problem into 9 groups (some may be empty). Call a bundle of edges all the edges that connect vertices of two different groups. In total, $\frac{9\cdot 8}{2}=36$ bundles of edges are formed (some bundles may contain no edges). Divide them into four groups of 9 bundles each as shown in the figures. In each group, the bundles of edges form three "triangles" that "cover" all 9 groups of vertices. In the graph $G$ there are at most $\frac{2012\cdot 8}{2}=8048$ edges, so in at least one of the four groups of bundles, the number of edges does not exceed $\frac{8048}{4}=2012$. Remove all the edges of this group. Whatever four vertices we now choose, by the pigeonhole principle at least two of them will fall into one of the formed "triangles". Clearly, such two vertices are not connected by an edge.