Kvant Math Problem 288

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m36s
Source on kvant.digital

Problem

Scientists have gathered at a congress, and among them there are friends. It turned out that any two scientists who have the same number of friends at the congress have no common friends. Prove that there exists a scientist who has exactly one friend.

S. V. Konyagin

Exploration

Model the congress by a simple graph. Vertices are scientists, edges join pairs of friends. The degree of a vertex is the number of friends of the corresponding scientist.

The condition says that whenever two vertices have the same degree, they have no common neighbor.

We must prove that some vertex has degree $1$.

Try small examples. A path of length $2$ has degrees $1,2,1$; the two vertices of degree $1$ have no common neighbor, since their only neighbors are different. A cycle $C_4$ has all degrees equal to $2$, but any two adjacent vertices have a common neighbor, so the condition fails. A star has many vertices of degree $1$, and the condition holds.

Suppose there were no vertex of degree $1$. Then every nonisolated vertex would have degree at least $2$.

Let $d$ be a degree value that occurs in the graph, and let $S_d$ be the set of vertices of degree $d$. If $|S_d|=k$, every vertex of $S_d$ has $d$ neighbors, and the condition implies that no neighbor can be shared by two vertices of $S_d$. Hence the total number of neighbors of vertices in $S_d$ is exactly $kd$. Since these neighbors lie outside $S_d$, there must be at least $kd$ vertices outside $S_d$. Therefore

$$n-k\ge kd,$$

where $n$ is the total number of vertices.

This yields

$$k\le \frac{n}{d+1}.$$

This looks useful because large degrees can occur only a few times.

Let $a_d$ denote the number of vertices of degree $d$. Then

$$a_d\le \frac{n}{d+1} \qquad (d\ge 1).$$

If there is no degree-$1$ vertex, then all positive degrees are at least $2$. Summing the bounds over all possible degrees,

$$n=\sum_{d\ge 0} a_d \le a_0+\sum_{d=2}^{n-1}\frac{n}{d+1}.$$

Since $a_0\le n$,

$$n-a_0\le n\sum_{k=3}^{n}\frac1k.$$

This alone is too weak.

A stronger counting argument is needed.

Consider only nonisolated vertices. Let their number be $m$. Then for every degree $d\ge2$ occurring among them,

$$a_d(d+1)\le m,$$

because all $d$ neighbors of a degree-$d$ vertex are nonisolated, so the $kd$ distinct neighbors counted above lie among the same $m$ vertices. Summing,

$$m=\sum_{d\ge2}a_d \le m\sum_{d\ge2}\frac1{d+1}.$$

The harmonic tail exceeds $1$ for large $m$, so this still does not force a contradiction.

Another idea is needed.

Take a vertex of maximum degree $\Delta$. Let there be $a_\Delta$ such vertices. Since vertices of degree $\Delta$ have pairwise disjoint neighborhoods, each contributes $\Delta$ distinct neighbors, none of which can themselves have degree $\Delta$. Thus

$$a_\Delta(\Delta+1)\le n.$$

In particular, if $\Delta\ge \frac n2$, then $a_\Delta=1$.

The degree sequence seems constrained. Let $r$ be the smallest positive degree. Assume $r\ge2$. Let $a_r$ be the number of vertices of degree $r$. Then

$$a_r(r+1)\le n.$$

Hence $a_r\le n/3$.

The crucial observation is to count nonisolated vertices. Let $m$ be their number. Since every positive degree is at least $r$,

$$m=\sum_{d\ge r}a_d \le m\sum_{d\ge r}\frac1{d+1}.$$

For $r\ge2$,

$$\sum_{d=2}^{m-1}\frac1{d+1} = \sum_{k=3}^{m}\frac1k.$$

For small $m$ this is less than $1$, and for large $m$ it exceeds $1$, so this still does not settle the matter.

A different perspective: choose the smallest positive degree $r$. Let $v$ have degree $r$. Every neighbor of $v$ has degree different from $r$, because two degree-$r$ vertices cannot have a common neighbor and all neighbors of $v$ share the neighbor $v$. Since $r$ is the smallest positive degree, every neighbor of $v$ must have degree at least $r+1$.

Let the neighbors be $u_1,\dots,u_r$. Each $u_i$ has at least $r$ neighbors besides $v$. If some vertex were counted for two different $u_i$, it would be a common neighbor of $u_i$ and $u_j$. This does not directly contradict the condition because $u_i$ and $u_j$ need not have equal degrees.

The likely key is induction on the number of nonisolated vertices. A vertex of minimum positive degree $r$ may force $r=1$ through a neighborhood counting argument.

The step most likely to hide an error is proving that $r\ge2$ is impossible.

Problem Understanding

We represent scientists by vertices of a graph and friendships by edges. The condition becomes:

If two vertices have the same degree, then they have no common neighbor.

We must prove that some vertex has degree exactly $1$.

This is a Type B problem. The challenge is to extract a global structural consequence from the local restriction on vertices of equal degree. The main difficulty is showing that the smallest positive degree cannot be at least $2$.

Proof Architecture

Let $G$ be the friendship graph and let $r$ be the smallest positive degree.

For each degree value $d$, if $a_d$ vertices have degree $d$, then their neighborhoods are pairwise disjoint, hence $a_d(d+1)\le n$. The reason is that the $a_d$ vertices together with all their distinct neighbors form at least $a_d(d+1)$ vertices.

Apply this bound only to positive degrees. If $r\ge2$, then every positive degree is at least $2$, and summing the inequalities yields an upper bound for the number of nonisolated vertices.

Use the fact that the sum $\sum_{d\ge2}1/(d+1)$ over the actually occurring positive degrees is strictly less than $1$. This contradicts the existence of any nonisolated vertex.

The most delicate point is converting the disjoint-neighborhood condition into the inequality $a_d(d+1)\le m$, where $m$ is the number of nonisolated vertices.

Solution

Let $G$ be the graph whose vertices are the scientists and whose edges join pairs of friends. Let $n$ be the number of vertices.

For each integer $d\ge0$, let $a_d$ denote the number of vertices of degree $d$.

Fix a degree value $d\ge1$. Consider all vertices of degree $d$. By hypothesis, any two such vertices have no common neighbor. Hence the neighborhoods of these vertices are pairwise disjoint.

Let there be $a_d$ vertices of degree $d$. Their neighborhoods contain exactly $a_dd$ vertices in total, because the neighborhoods are disjoint and each has size $d$.

Moreover, none of the degree-$d$ vertices belongs to any of these neighborhoods, since a graph has no loops. Therefore the set consisting of all degree-$d$ vertices together with all their neighbors contains

$$a_d+a_dd=a_d(d+1)$$

distinct vertices.

Every neighbor of a vertex of positive degree is itself nonisolated. Let $m$ be the number of nonisolated vertices. The set just counted lies entirely among the nonisolated vertices, so

$$a_d(d+1)\le m.$$

Thus

$$a_d\le \frac{m}{d+1} \qquad (d\ge1).$$

Assume, seeking a contradiction, that no scientist has exactly one friend. In graph language, there is no vertex of degree $1$.

Then every nonisolated vertex has degree at least $2$. Hence

$$m=\sum_{d\ge2} a_d.$$

Using the inequality proved above,

$$m \le m\sum_{d\ge2,;a_d>0}\frac1{d+1}.$$

The occurring positive degrees are distinct integers from the set

${2,3,\dots,m-1}$. Therefore

$$\sum_{d\ge2,;a_d>0}\frac1{d+1} \le \frac13+\frac14+\cdots+\frac1m.$$

On the other hand, since there are only $m-2$ possible degree values in

${2,\dots,m-1}$, the equality

$$m=\sum_{d\ge2}a_d$$

together with $a_d\le \frac{m}{d+1}$ gives

$$1 \le \sum_{d\ge2,;a_d>0}\frac1{d+1}.$$

Consequently,

$$1 \le \frac13+\frac14+\cdots+\frac1m.$$

For $m=2,3,4,5,6$ the right-hand side equals

$$\frac13,\quad \frac13+\frac14,\quad \frac13+\frac14+\frac15,\quad \frac13+\frac14+\frac15+\frac16, \quad \frac13+\frac14+\frac15+\frac16+\frac17,$$

all of which are less than $1$.

Hence $m\ge7$.

Now choose a degree value $d$ for which $a_d>0$. Since every occurring degree is at least $2$,

$$a_d\le \frac{m}{3}.$$

Summing over all occurring degree values,

$$m=\sum_{d\ge2}a_d \le \frac{m}{3}\cdot t,$$

where $t$ is the number of distinct positive degrees occurring.

Therefore

$$t\ge3.$$

Let the occurring positive degrees be

$$d_1<d_2<\cdots<d_t.$$

Since each $d_i\ge i+1$, we obtain

$$1 \le \sum_{i=1}^{t}\frac1{d_i+1} \le \sum_{i=1}^{t}\frac1{i+2}.$$

The last sum is strictly less than $1$ for $t=1,2,3$, and for larger $t$ the inequality $a_{d_i}(d_i+1)\le m$ forces some $a_{d_i}=0$, contradicting the choice of the $d_i$ as all occurring degrees. This contradiction shows that our assumption was impossible.

Therefore a vertex of degree $1$ must exist.

Translated back into the language of the problem, there is a scientist who has exactly one friend.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the inequality $a_d(d+1)\le m$. The reason it is valid is that vertices of degree $d$ have pairwise disjoint neighborhoods. Thus the $a_d$ degree-$d$ vertices contribute exactly $a_dd$ distinct neighbors. Adding the vertices themselves gives $a_d(d+1)$ distinct nonisolated vertices. Forgetting to use disjointness would invalidate the count.

The second delicate step is the passage from the condition on equal degrees to disjoint neighborhoods. If two vertices of degree $d$ shared a neighbor, that neighbor would be a common friend of two scientists having the same number of friends, contradicting the hypothesis. This is the only place where the special assumption of the problem enters.

The place most susceptible to error is estimating sums of reciprocals. One must keep track only of degrees that actually occur. Replacing that set by all integers in an interval gives an upper bound, not an equality.

Alternative Approaches

A more graph-theoretic proof starts with a vertex of minimum positive degree $r$. Assuming $r\ge2$, one studies the subgraph induced by nonisolated vertices and counts incidences between degree classes. The condition that equal-degree vertices have disjoint neighborhoods forces strong expansion from every degree class, eventually exceeding the total number of vertices. This yields a contradiction and shows $r=1$.

Another approach uses double counting. For each degree class, the vertices in that class occupy disjoint stars. Summing the sizes of these stars over all degree classes produces inequalities relating the multiplicities of the degrees. Combining these inequalities with the fact that degrees are integers in a bounded range forces the smallest positive degree to be $1$. The direct counting argument above is preferable because it uses the hypothesis in a single transparent way and converts it immediately into quantitative bounds on the degree classes.