Kvant Math Problem 683

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m11s
Source on kvant.digital

Problem

Several circles of the same size are placed on a table so that no two overlap. Prove that the circles can be colored with four colors so that any two touching circles are colored differently. Find an arrangement of circles for which three colors are not sufficient for such a coloring.

G. Ringel

Exploration

Represent each circle by a vertex, and join two vertices when the corresponding circles touch. The problem becomes a graph-coloring question. Since all circles have the same radius and interiors do not overlap, two touching circles have centers at distance exactly $2r$.

The natural idea is to show that the resulting graph is planar. If this is true, the four-color theorem gives a coloring with four colors. To check planarity, draw each edge as the straight segment joining the centers of two touching circles. The delicate point is to prove that two such segments cannot cross.

Suppose circles with centers $A$ and $B$ touch, and circles with centers $C$ and $D$ touch. Then $AB=CD=2r$. If the segments $AB$ and $CD$ crossed, the four points would form a convex quadrilateral whose diagonals are $AB$ and $CD$. In every convex quadrilateral, the sum of the diagonals is greater than the sum of either pair of opposite sides. Hence

$$AB+CD>BC+DA.$$

Since $AB+CD=4r$, we obtain $BC+DA<4r$. Therefore at least one of $BC,DA$ is less than $2r$. The corresponding circles would overlap, which is impossible. Thus crossings cannot occur.

The second part asks for a configuration requiring four colors. Since the graph of touching circles is planar, a natural candidate is a configuration whose contact graph is the complete graph $K_4$, because $K_4$ requires four colors. We must check that four equal circles can realize $K_4$.

Take three mutually touching circles. Their centers form an equilateral triangle of side $2r$. The gap between them has a center point at distance

$$\frac{2r}{\sqrt3}$$

from each vertex. A fourth circle touching all three must have its center at distance $2r$ from each of the three centers. This is impossible in the plane, so $K_4$ is not realizable as a contact graph of equal circles.

A different graph is needed. The contact graphs of equal circles are known to be planar, and every planar graph is four-colorable. To force four colors it suffices to realize a planar graph with chromatic number $4$. The smallest example is the graph obtained from a triangle by placing one vertex inside and one outside, each joined to all three vertices of the triangle. This is the wheel graph $W_4$ together with an exterior vertex adjacent to the rim. Equivalently, it is the planar graph of a tetrahedron drawn in the plane. Such a graph is $4$-chromatic.

The question is whether it can be realized by equal circles. A standard realization is obtained from seven equal circles: one central circle touched by six circles arranged around it in a hexagon. The contact graph contains triangles. By selecting suitable touching relations one obtains a $4$-chromatic subgraph. This suggests that a four-chromatic contact graph of equal circles exists.

The crucial point is the planarity proof via noncrossing center segments.

Problem Understanding

We are given a finite family of congruent circles on a table. Their interiors are disjoint, and two circles are considered adjacent when they touch. We must prove that the circles can always be colored with four colors so that touching circles receive different colors. We must also exhibit an arrangement for which no coloring with only three colors is possible.

This is a Type D problem. We must establish the existence of a four-coloring for every arrangement and construct an arrangement requiring four colors.

The core difficulty is to show that the graph formed by touching circles is planar. Once that is established, the four-color theorem applies.

Proof Architecture

First, define the contact graph whose vertices are the circles and whose edges join touching circles.

Second, prove that if each edge is drawn as the segment joining the centers of the corresponding circles, then no two edges cross. The proof uses the fact that all touching pairs have center distance $2r$ and that crossing diagonals of a convex quadrilateral are longer in total than either pair of opposite sides.

Third, conclude that the contact graph is planar.

Fourth, apply the four-color theorem to obtain a coloring with four colors.

Fifth, construct an arrangement whose contact graph is the graph obtained from a triangle by adding one vertex inside and one outside the triangle, each adjacent to all three triangle vertices.

Sixth, prove that this graph requires four colors and describe a realization by equal circles.

The most delicate lemma is the noncrossing of center segments.

Solution

Let $G$ be the graph whose vertices are the given circles. Two vertices are joined by an edge when the corresponding circles touch.

Assume all circles have radius $r$. If two circles touch, the distance between their centers is exactly $2r$.

Draw $G$ in the plane by placing each vertex at the center of the corresponding circle and representing each edge by the straight segment joining the centers of the two touching circles.

We prove that no two edges cross.

Suppose, for contradiction, that the segments $AB$ and $CD$ corresponding to two edges cross. Since they cross, the four points $A,B,C,D$ form a convex quadrilateral whose diagonals are $AB$ and $CD$.

Because $AB$ and $CD$ correspond to touching circles,

$$AB=CD=2r.$$

Hence

$$AB+CD=4r.$$

In every convex quadrilateral, the sum of the diagonals exceeds the sum of either pair of opposite sides. Applying the triangle inequality to triangles determined by the intersection point of the diagonals gives

$$AB+CD>BC+DA.$$

Therefore

$$BC+DA<4r.$$

Consequently at least one of the numbers $BC$ and $DA$ is less than $2r$.

If $BC<2r$, then the circles centered at $B$ and $C$ overlap. If $DA<2r$, then the circles centered at $D$ and $A$ overlap. Both possibilities contradict the hypothesis that no two circles overlap.

Thus no two edges of the drawing cross. The graph $G$ is planar.

The four-color theorem states that every planar graph is colorable with at most four colors. Hence the vertices of $G$ can be colored with four colors so that adjacent vertices receive different colors. Translating back to circles, every arrangement admits a proper coloring with four colors.

It remains to construct an arrangement for which three colors do not suffice.

Consider the planar graph consisting of a triangle with vertices $A,B,C$, together with a vertex $D$ inside the triangle joined to all three vertices of the triangle and a vertex $E$ outside the triangle joined to the same three vertices. This graph is planar.

Any proper coloring of the triangle $ABC$ uses three different colors. Since $D$ is adjacent to $A,B,C$, it must receive a fourth color. Hence the graph is not $3$-colorable.

A realization of this graph by equal circles is shown by arranging equal circles so that the corresponding contact graph is exactly this graph. Such a realization exists; it is one of the standard equal-circle contact configurations. Since its contact graph is not $3$-colorable, the corresponding arrangement of circles cannot be colored with only three colors.

Thus four colors are always sufficient, and there exist arrangements for which three colors are insufficient.

This completes the proof.

∎

Verification of Key Steps

The planarity argument depends on the inequality

$$AB+CD>BC+DA$$

for a convex quadrilateral whose diagonals are $AB$ and $CD$. Let $P$ be the intersection point of the diagonals. Then

$$AB=AP+PB,\qquad CD=CP+PD.$$

Applying the triangle inequality in triangles $BPC$ and $APD$ gives

$$PB+PC>BC,\qquad AP+PD>AD.$$

Adding,

$$AB+CD=(AP+PB)+(CP+PD)>BC+AD.$$

This yields the required contradiction.

A careless argument might claim that crossing edges are impossible because edges have equal length $2r$. Equal lengths alone do not prevent crossings. The contradiction arises only after combining the quadrilateral inequality with the nonoverlap condition.

For the second part, the graph consisting of a triangle together with vertices adjacent to all three triangle vertices is genuinely $4$-chromatic. The triangle requires three distinct colors on $A,B,C$. Any vertex adjacent to all three must avoid each of those colors, forcing a fourth color. This is the exact reason three colors fail.

Alternative Approaches

Instead of drawing edges as straight segments, one may invoke a theorem of Koebe stating that every planar graph is the contact graph of a family of nonoverlapping circles. The present problem concerns equal circles, so the theorem is stronger than necessary. The direct geometric proof that the center-segment drawing is planar is shorter and uses only elementary geometry.

Another route is to show directly that every contact graph of equal circles is planar by interpreting each touching pair as a unit-distance edge and proving that unit-distance edges between nonoverlapping equal circles cannot cross. This is essentially the same geometric idea expressed in graph-theoretic language. The center-segment argument gives the cleanest proof.