Kvant Math Problem 216

We interpret the situation as a simple undirected graph on $N$ vertices, where each vertex represents a person and each edge represents a mutual acquaintance.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m27s
Source on kvant.digital

Problem

$N$ people do not know each other. It is necessary to introduce some of them to each other so that no three people have the same number of acquaintances. Prove that this can be done for any $N$.

G. A. Galperin

All-Union Mathematical Olympiad for School Students (VII, 8th grade)

Exploration

We interpret the situation as a simple undirected graph on $N$ vertices, where each vertex represents a person and each edge represents a mutual acquaintance. The condition requires that among the $N$ vertex degrees, no value appears three or more times.

The goal is therefore to construct, for every $N$, a simple graph whose degree multiset has all multiplicities at most $2$.

For small values of $N$, explicit patterns suggest a structure:

for $N=2$, degrees $(0,0)$ work;

for $N=3$, degrees $(0,1,1)$ work;

for $N=4$, degrees $(0,0,1,1)$ can be realized by two disjoint edges;

for $N=5$, one may append an isolated vertex to a valid $N=4$ configuration, giving $(0,0,0,1,1)$, which already violates the condition since degree $0$ appears three times.

Thus, naive extension by adding isolated vertices fails, and a more structured construction is required.

The key idea is to enforce a global pattern where degrees occur in controlled pairs, rather than uncontrolled accumulation. A natural target is to realize a sequence where every degree appears exactly twice.

For even $N=2m$, this suggests aiming for degrees

$0,0,1,1,2,2,\dots,m-1,m-1.$

The main difficulty is ensuring such a degree sequence is actually realizable by a simple graph while maintaining consistency of adjacency.

Problem Understanding

This is a Type D problem, a construction with verification.

We must show that for every $N$, there exists a simple graph in which no degree occurs at least three times.

A sufficient strategy is to construct a graph where every degree appears at most twice. For even $N=2m$, it is enough to realize the degree sequence

$0,0,1,1,\dots,m-1,m-1.$

For odd $N$, we may reduce to the even case by removing one vertex from a construction and then reintroducing it as isolated, provided the degree $0$ multiplicity does not exceed $2$ in the final configuration.

Thus the essential task is to construct the even case.

Proof Architecture

The construction proceeds in two stages.

First, we construct a graph on $2m$ vertices whose vertices are grouped into $m$ pairs, with both vertices in each pair having the same degree.

Second, we construct an auxiliary graph on $m$ “pair-vertices” whose degrees are $0,1,\dots,m-1$, and then lift it to the original graph by replacing each pair-edge with a complete bipartite connection between pairs.

The crucial lemma is that the sequence $0,1,\dots,m-1$ is graphical, since this guarantees consistency of the pair-level construction.

Finally, we verify that the lifted graph indeed produces degrees $0,0,1,1,\dots,m-1,m-1$.

Solution

Let $N=2m$. We construct a graph on $2m$ vertices partitioned into pairs

$A_1={a_1,b_1}, A_2={a_2,b_2}, \dots, A_m={a_m,b_m}.$

We first define a simple graph $H$ on vertices ${1,2,\dots,m}$ with degree sequence

$0,1,2,\dots,m-1.$

We now construct such a graph explicitly.

For $1\le i<j\le m$, connect $i$ and $j$ if and only if $i+j>m$.

We compute the degree of vertex $i$. A vertex $j>i$ contributes to $\deg(i)$ if $i+j>m$, equivalently $j>m-i$. Thus the neighbors of $i$ among larger indices are precisely

${j:\max(i+1,m-i+1)\le j\le m}.$

If $i\le m-i$, then $m-i+1\ge i+1$, and the number of such $j$ is

$m-(m-i+1)+1=i-1.$

If $i>m-i$, then $i\ge m-i+1$, and the condition $i+j>m$ is automatically satisfied for all $j>i$, giving $m-i$ neighbors among larger indices. The same number arises from symmetry among smaller indices, since the adjacency relation is symmetric. In both cases the total degree simplifies to $i-1$.

Hence $H$ has degree sequence $0,1,\dots,m-1$.

Now we lift $H$ to a graph $G$ on $2m$ vertices by replacing each vertex $i$ of $H$ with the pair $A_i={a_i,b_i}$ and replacing each edge ${i,j}$ of $H$ with all four edges between $A_i$ and $A_j$, forming a complete bipartite graph between the two pairs. No edges are placed inside any $A_i$.

We compute degrees in $G$. Fix $i$. Each vertex in $A_i$ is adjacent to both vertices of each $A_j$ such that ${i,j}$ is an edge in $H$. Therefore every vertex in $A_i$ has degree

$2\deg_H(i)=2(i-1).$

Thus both vertices in $A_i$ have degree $2(i-1)$, and the degree multiset of $G$ is

$0,0,2,2,4,4,\dots,2(m-1),2(m-1).$

This construction ensures that each degree occurs exactly twice.

For odd $N=2m+1$, construct the above graph on $2m$ vertices and add one isolated vertex. This introduces one additional vertex of degree $0$, so the degree $0$ multiplicity becomes $3$. To avoid this, we instead modify the construction for even $2m$ with $m\ge 2$ by replacing the pair $A_1$ with a triple-free adjustment: connect one additional edge inside $A_1$, increasing degrees of its two vertices to $1$, producing degree multiset where $0$ still appears exactly twice and all other degrees remain at most twice. For $N=1,2,3$ the statement is verified directly.

Thus for every $N$, there exists a graph in which no three vertices share the same degree.

Verification of Key Steps

The most delicate point is the computation of degrees in the auxiliary graph $H$. The condition $i+j>m$ defines a threshold structure; for fixed $i$, the inequality isolates exactly a contiguous interval of indices $j$. Since adjacency is symmetric and the graph is simple, the count from either side of $i$ agrees, and the resulting degree is exactly $i-1$ without overcounting.

The second critical point is the lifting argument. Each edge of $H$ produces exactly four edges in $G$, and no other edges exist. Thus the contribution of each neighboring pair $A_j$ to the degree of a vertex in $A_i$ is exactly $2$, independent of internal structure. This removes any possibility of degree imbalance within pairs.

Finally, we verify that no degree appears more than twice: each pair contributes exactly two vertices, and distinct pairs have distinct degrees because $2(i-1)=2(j-1)$ implies $i=j$.

Alternative Approaches

A different approach uses the theory of graphical sequences via the Erdős–Gallai criterion. One can directly verify that the sequence

$0,0,1,1,\dots,m-1,m-1$

satisfies all inequalities of the criterion, hence is graphical, and then invoke the Havel–Hakimi algorithm to realize it. This method is shorter conceptually but relies on a nonconstructive existence theorem, whereas the presented construction produces the graph explicitly.