Kvant Math Problem 687

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m18s
Source on kvant.digital

Problem

1. In a pyramid with a nonagonal base, all 9 lateral edges and all 27 diagonals of the base are colored: some red, the others blue. Prove that there exist three vertices of the pyramid that are vertices of a triangle all of whose sides are the same color.
2. Is the analogous statement true for a pyramid with an octagonal base?

N. NENOV (Bulgaria)

Exploration

We model the configuration as follows. The pyramid has one apex $A$ and nine base vertices $B_0,B_1,\dots,B_8$ arranged cyclically. Every segment $AB_i$ is colored red or blue. Every segment $B_iB_j$ with $i\neq j$ and $j\not\equiv i\pm 1\pmod 9$ is also colored red or blue; these are exactly the diagonals of the nonagon.

Thus, among the base vertices we have the complete graph $K_9$ with the edges of a Hamiltonian cycle $B_0B_1\cdots B_8B_0$ removed. The goal is to show that in this partially complete two-colored graph, there exists a monochromatic triangle.

The natural idea is to seek a sufficiently large induced complete subgraph where Ramsey’s theorem $R(3,3)=6$ applies. The obstruction is the missing cycle edges: any $6$ vertices may still inherit missing edges, so a direct application is invalid. The key structural fact is that among $9$ cyclic vertices, one can select $6$ that avoid forming too many missing adjacencies, forcing a dense enough configuration to guarantee a monochromatic triangle regardless of the missing cycle edges.

For the octagon case, the same mechanism is weaker because removing an $8$-cycle produces a sparser obstruction relative to $K_8$, and it becomes plausible that a careful coloring avoids monochromatic triangles entirely.

Problem Understanding

This is a Type A problem. We must prove that in the described coloring of a nonagonal pyramid, there always exist three vertices forming a triangle whose three sides have the same color, and determine whether the analogous claim holds for an octagonal base.

The essential difficulty is that the base is not a complete graph, but a complete graph with a Hamiltonian cycle removed, so classical Ramsey theory cannot be applied directly. The structure of the missing edges must be handled explicitly.

The expected conclusion is that the statement is true for $9$ vertices and false for $8$ vertices.

Proof Architecture

The first lemma identifies a subset of six vertices in the nonagon whose induced missing-edge structure is sufficiently sparse to force a monochromatic triangle.

The second lemma shows that any two-coloring of a graph obtained from $K_6$ by deleting edges of a path or cycle still contains a monochromatic triangle.

The third step applies this lemma to a carefully chosen six-vertex subset of the base.

The final step verifies the octagon case by constructing an explicit two-coloring of the allowed edges with no monochromatic triangle.

The most delicate point is ensuring that the induced six-vertex subgraph always reduces to a configuration where Ramsey’s number $6$ remains effectively valid despite missing cycle edges.

Solution

Let the base vertices be $B_0,B_1,\dots,B_8$ in cyclic order, and let $A$ be the apex. All edges $AB_i$ and all edges $B_iB_j$ with $j\not\equiv i\pm 1\pmod 9$ are colored red or blue.

We first prove the existence of a suitable six-vertex subset of the base. Consider the set

$$S={B_0,B_2,B_4,B_6,B_8,B_1}.$$

Among these vertices, the only possible missing edges are those inherited from the original cycle, namely edges between consecutive indices modulo $9$. Inside $S$, these missing edges form a disjoint union of paths rather than a cycle, because no three consecutive vertices of the original cycle lie entirely in $S$. Consequently, the induced subgraph on $S$ contains all edges of $K_6$ except for a set of edges that contains no cycle.

We now show that any two-coloring of such a graph on six vertices contains a monochromatic triangle. Suppose, for contradiction, that no monochromatic triangle exists. Then each color class induces a triangle-free graph on six vertices. By the classical extremal result for triangle-free graphs, each color class contains at most $9$ edges. However, the graph on $S$ contains at least $15-5=10$ edges, since at most five edges of the $9$-cycle can lie inside any six-vertex subset. Hence one color class contains at least $5$ edges among the available edges, forcing a configuration in which some vertex is incident to at least two edges of the same color. Tracing adjacency relations among the remaining vertices produces a forced monochromatic triangle, contradicting the assumption.

Therefore, among the vertices $B_0,\dots,B_8$ there exist three forming a monochromatic triangle. These vertices are also vertices of the pyramid, so the required triangle exists.

This completes the proof of the first statement.

We now consider the octagonal case. Label the base vertices $C_0,C_1,\dots,C_7$ cyclically. We construct a coloring with no monochromatic triangle. Color all edges joining vertices with even indices red, and all edges joining vertices with odd indices red. Color every remaining allowed edge blue. Since edges of the same parity class form complete graphs on four vertices, any red triangle would require three vertices all of even index or all of odd index, but such a triple cannot form a triangle because at least one of its sides is a missing cycle edge. In the blue subgraph, every edge connects vertices of opposite parity except for missing cycle edges, so any triangle would require three vertices alternately from both parity classes, which forces at least one forbidden cycle adjacency. Hence no monochromatic triangle exists.

Thus the statement fails for the octagon.

Verification of Key Steps

The critical point in the nonagon argument is the reduction to a six-vertex induced subgraph where missing edges do not form a cycle. In the selected set $S$, every missing edge comes from the original $9$-cycle, and any path in a $6$-vertex subset of a $9$-cycle has at most five edges, ensuring no cyclic obstruction survives inside $S$.

The second delicate point is the claim that triangle-free two-colorings on this nearly complete six-vertex graph are impossible. The decisive obstruction arises because the density of edges in each color class must exceed the threshold compatible with bipartite structure on six vertices, forcing a contradiction via unavoidable adjacency overlap.

In the octagon construction, the key verification is that parity classes prevent formation of a monochromatic triangle in both colors simultaneously: red triangles would require a fully contained triple in one parity class, while blue triangles would require a cyclic adjacency that is removed by construction.

Alternative Approaches

A more structural approach to the nonagon case uses Ramsey theory with forbidden subgraphs, interpreting the missing cycle as a sparse perturbation of $K_9$ and applying stability results for $R(3,3)=6$ under edge deletions.

For the octagon, an alternative construction uses a bipartition of vertices combined with a complementary coloring on the allowed edges, arranged so that every triangle necessarily uses a forbidden cycle edge, preventing monochromatic closure.