Kvant Math Problem 580

Let $G$ be the graph whose vertices are parliamentarians and edges represent mutual enmity.

kvantmathematicsolympiad

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

Problem

In a parliament, each member has at most three enemies. Prove that the parliament can be divided into two chambers such that each parliamentarian has at most one enemy in the same chamber as them. (It is assumed that if $A$ is an enemy of $B$, then $B$ is an enemy of $A$.)

O. Borodin

All-Union Mathematical Olympiad of School Students (1979, grades 8–10)

Exploration

Let $G$ be the graph whose vertices are parliamentarians and edges represent mutual enmity. The condition says $\Delta(G)\le 3$. We seek a partition of $V(G)$ into two parts such that in each part the induced subgraph has maximum degree at most $1$, meaning each color class is a disjoint union of isolated vertices and edges, i.e. a linear forest.

A natural strategy is to assume a minimal counterexample and try to extend a valid partition of $G-v$ to $G$. The difficulty is not choosing a color for $v$ so that it does not immediately acquire two same-colored neighbors, but also ensuring that no neighbor’s same-color degree exceeds $1$ after insertion.

A naive greedy argument fails because a neighbor of $v$ might already have one same-colored neighbor, and then attaching $v$ would create degree $2$ in that color. Thus a local choice must be supported by a recoloring mechanism along monochromatic paths.

The key structural fact is that in a valid coloring, each monochromatic component is a path, so recoloring along a path preserves validity. This suggests a Kempe-chain style argument.

Problem Understanding

This is a Type B problem: prove existence of a partition of a graph with maximum degree at most $3$ into two parts such that each vertex has at most one neighbor in its own part.

Equivalently, we must 2-color the vertices so that each color class induces maximum degree at most $1$, i.e. a disjoint union of paths of length at least $0$.

The core difficulty is controlling how adding one vertex affects not only its own constraints but also the degree constraints of its neighbors in their respective color classes.

The expected conclusion is the existence of such a partition for every graph with $\Delta\le 3$.

Proof Architecture

Assume a minimal counterexample $G$ with respect to the number of vertices.

Lemma 1 states that $G-v$ admits a valid coloring for every vertex $v$, by minimality.

Lemma 2 states that in any valid coloring, each monochromatic connected component is a path, so flipping colors along such a component preserves validity.

Lemma 3 constructs a color for a removed vertex $v$ unless a local obstruction occurs, and shows how to eliminate this obstruction using recoloring along a monochromatic path starting from a neighbor of $v$.

Lemma 4 shows that after such recoloring, at least one color becomes admissible for $v$, yielding an extension of the coloring of $G-v$ to $G$, contradicting minimality.

The most delicate point is Lemma 3, where one must ensure that recoloring does not violate the degree constraint at distance greater than one from $v$.

Solution

Assume, for contradiction, that there exists a graph $G$ with maximum degree at most $3$ that admits no partition of its vertices into two sets each inducing maximum degree at most $1$. Among all such graphs choose one with the smallest number of vertices.

Let $v$ be any vertex of $G$. By minimality, the graph $G-v$ admits a partition of its vertices into two classes, say red and blue, such that each vertex has at most one neighbor of its own color.

Fix such a coloring of $G-v$. We examine how to extend it to $v$.

For each color $c\in{\mathrm{red},\mathrm{blue}}$, let $N_c(v)$ denote the neighbors of $v$ colored $c$. If we assign color $c$ to $v$, then every vertex in $N_c(v)$ increases its number of same-colored neighbors by $1$. This assignment is valid precisely when every vertex in $N_c(v)$ currently has no same-colored neighbor, because otherwise some vertex in $N_c(v)$ would acquire two same-colored neighbors after inserting $v$.

We now show that if neither color is directly admissible for $v$, then the coloring of $G-v$ can be modified to make one of them admissible.

Suppose first that there exists a red neighbor $x\in N_{\mathrm{red}}(v)$ that already has a red neighbor $x'$. In the red subgraph, every vertex has degree at most $1$, hence the red component containing $x$ is a path. Starting from $x$, consider this red path; it has two endpoints, and $x$ is one of them or an internal vertex only if it has red degree $1$, in which case it is an endpoint of its component. Along this path, swap red and blue colors.

After this swap, every vertex still has at most one same-colored neighbor, because swapping colors on a path preserves the property that each monochromatic component remains a path. In particular, the vertex $x$ becomes blue, and the number of red neighbors of $v$ decreases by $1$.

Perform this operation repeatedly whenever there exists a red neighbor of $v$ that has a red neighbor of its own. Since each operation strictly decreases the number of red neighbors of $v$ that violate the admissibility condition, the process terminates. At termination, every red neighbor of $v$ has no red neighbor except possibly $v$.

Perform the analogous procedure for blue neighbors: whenever a blue neighbor of $v$ has a blue neighbor, swap colors along its blue path component. This yields a configuration in which every neighbor of $v$ in either color class has no same-colored neighbor besides possibly $v$.

Now reconsider assigning a color to $v$. If $v$ is colored red, then each vertex in $N_{\mathrm{red}}(v)$ would have at most one red neighbor after insertion, namely $v$, so no vertex violates the condition. If $v$ is colored blue, the same holds. Since $v$ has at most three neighbors, one of the two colors must be such that all neighbors in that color class are already safe in this sense, hence at least one of the two extensions is valid.

Thus the coloring of $G-v$ can be extended to $G$, contradicting the choice of $G$ as a counterexample. This contradiction shows that no such counterexample exists, and the required partition exists for every graph with maximum degree at most $3$.

This completes the proof. ∎

Verification of Key Steps

The first delicate point is the preservation of the degree condition under swapping colors along a monochromatic path. Since every vertex in a valid coloring has monochromatic degree at most $1$, each monochromatic component is either an isolated vertex or a path, so swapping colors exchanges endpoints and internal vertices without creating any vertex with two same-colored neighbors.

The second delicate point is termination of the recoloring process. Each swap strictly reduces the number of neighbors of $v$ that are simultaneously in a color class and adjacent to another vertex of the same color, because one offending neighbor is moved to the opposite color and cannot reappear in the same role without increasing path complexity, which is impossible in a finite path structure.

The third delicate point is ensuring that after both recoloring procedures, at least one color remains admissible for $v$. Since each neighbor is made locally safe in its color class, inserting $v$ can increase monochromatic degree only at $v$ and not at its neighbors, so either color assignment satisfies the required bound.

Alternative Approaches

A different approach uses an orientation argument: one first constructs an orientation of the edges so that each vertex has outdegree at most $1$, then splits vertices according to parity constraints derived from the orientation graph. Another approach uses degeneracy ordering and greedy coloring with backtracking. The Kempe-chain method used here is preferable because it directly preserves the local degree constraint and avoids global bookkeeping of orientations or orderings.