Kvant Math Problem 76

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m13s
Source on kvant.digital

Problem

In a group of $n$ people, every pair of strangers has exactly two mutual acquaintances, and every pair of acquaintances has no more than two mutual acquaintances. Prove that in this group, each person knows the same number of people.

Exploration

Represent the group by a simple graph. Vertices are people, adjacent vertices are acquaintances, and nonadjacent vertices are strangers. The assumptions become:

For every nonadjacent pair of vertices, the number of common neighbors is exactly $2$.

For every adjacent pair of vertices, the number of common neighbors is at most $2$.

The conclusion is that the graph is regular.

A natural idea is to compare the degrees of two vertices. Let $u$ have minimum degree $m$, and let $v$ be any neighbor of $u$. Since $u$ has minimum degree, $\deg v \ge m$. The problem is to show equality.

Let $A=N(u)\setminus{v}$, so $|A|=m-1$. Every vertex $x\notin N(u)\cup{u}$ is a stranger of $u$, hence has exactly two neighbors in $N(u)$. Counting incidences between such vertices and $N(u)$ may relate degrees to the number of common neighbors of adjacent pairs.

For a fixed neighbor $v$ of $u$, let $t$ be the number of common neighbors of $u$ and $v$. Then $t\le2$. The degree of $v$ equals

$$\deg v=1+t+s,$$

where $s$ is the number of neighbors of $v$ outside $N(u)\cup{u}$.

Every such outside neighbor $x$ is a stranger of $u$, so among the neighbors of $u$ it has exactly two neighbors. Counting pairs $(x,w)$ with $x$ outside and $w\in N(u)$ adjacent to $x$, each outside vertex contributes exactly $2$.

Let

$$B=V\setminus (N(u)\cup{u}),$$

so $|B|=n-m-1$. Counting incidences between $B$ and $N(u)$ gives

$$2|B|=\sum_{w\in N(u)}(\deg w-1-c_w),$$

where $c_w$ is the number of common neighbors of $u$ and $w$. Since $c_w\le2$ and $\deg w\ge m$,

$$2(n-m-1)\ge \sum_{w\in N(u)}(m-3)=m(m-3).$$

On the other hand, every vertex of $B$ has exactly two neighbors in $N(u)$, suggesting a second count involving pairs of neighbors of $u$. Since each pair of acquaintances in $N(u)$ contributes a common neighbor of $u$, and each pair of nonadjacent vertices in $N(u)$ contributes another common neighbor structure, there may be a tight inequality forcing $c_w=2$ and $\deg w=m$.

The crucial point is to obtain an exact formula for $\sum c_w$. Let $e$ be the number of edges inside $N(u)$. Every edge inside $N(u)$ is counted twice in $\sum c_w$, because if $xy$ is such an edge then $y$ contributes to $c_x$ and $x$ contributes to $c_y$. Hence

$$\sum_{w\in N(u)} c_w = 2e.$$

Now count pairs of vertices in $N(u)$. There are $\binom m2$ such pairs. Every nonedge inside $N(u)$ has exactly one common neighbor already known, namely $u$, and by hypothesis a pair of strangers has exactly two common neighbors altogether. Thus every nonedge inside $N(u)$ determines exactly one vertex of $B$ adjacent to both ends. Conversely, a vertex of $B$ is adjacent to exactly two vertices of $N(u)$, so it determines exactly one such nonedge. Therefore

$$|B|=\binom m2-e.$$

This is the key identity.

Substituting $e=\binom m2-|B|$ into $\sum c_w=2e$ yields

$$\sum_{w\in N(u)} c_w = m(m-1)-2|B| = m(m-1)-2(n-m-1).$$

Combining with the earlier incidence count

$$2|B| =\sum_{w\in N(u)}(\deg w-1-c_w),$$

gives

$$2(n-m-1) =\sum_{w\in N(u)}(\deg w-1)-\sum c_w.$$

After substitution, all $n$ terms cancel and one gets

$$\sum_{w\in N(u)}\deg w=m^2.$$

Since each $\deg w\ge m$ and there are $m$ neighbors of $u$, equality of the sum with $m^2$ forces every neighbor of $u$ to have degree exactly $m$.

Then any vertex in $B$ is adjacent to two neighbors of $u$, each of degree $m$. Repeating the same argument with one of those neighbors as the minimum degree vertex should show the vertex in $B$ also has degree $m$. That yields regularity.

Problem Understanding

We are given a graph in which every nonadjacent pair of vertices has exactly two common neighbors, while every adjacent pair has at most two common neighbors. The task is to prove that all vertices have the same degree.

This is a Type B problem. The statement is already specified, and we must prove it.

The core difficulty is to derive enough global information from the local condition on common neighbors. The decisive step is to choose a vertex of minimum degree and prove that every one of its neighbors has exactly the same degree. This requires a careful double counting argument.

Proof Architecture

Let $u$ be a vertex of minimum degree $m$.

Define $B$ to be the set of vertices not adjacent to $u$; every vertex of $B$ has exactly two neighbors in $N(u)$, because each such vertex is a stranger of $u$.

Show that the number of nonedges inside $N(u)$ equals $|B|$, by associating to every nonadjacent pair in $N(u)$ its unique common neighbor outside $N(u)\cup{u}$.

Deduce an exact expression for the total number of common neighbors shared by $u$ and its neighbors.

Count incidences between $B$ and $N(u)$ in a second way and obtain the identity

$$\sum_{w\in N(u)}\deg w=m^2.$$

Since $u$ has minimum degree, every neighbor of $u$ has degree at least $m$; the preceding identity then forces every neighbor of $u$ to have degree exactly $m$.

Finally, every vertex not adjacent to $u$ is adjacent to two neighbors of $u$, both of degree $m$. Since $m$ is the minimum degree, these neighbors have minimum degree, and applying the previous conclusion to either of them shows that the given vertex also has degree $m$.

The lemma most likely to fail under scrutiny is the bijection between nonedges inside $N(u)$ and vertices of $B$; it must be proved in both directions.

Solution

Consider the graph whose vertices are the people in the group and whose edges join pairs of acquaintances. The assumptions become:

Every nonadjacent pair of vertices has exactly two common neighbors.

Every adjacent pair of vertices has at most two common neighbors.

Let $u$ be a vertex of minimum degree, and let

$$m=\deg u.$$

Denote the neighborhood of $u$ by $N(u)$, and put

$$B=V\setminus\bigl(N(u)\cup{u}\bigr).$$

Thus $|B|=n-m-1$.

Take any vertex $x\in B$. Since $x$ and $u$ are nonadjacent, they have exactly two common neighbors. Every common neighbor of $x$ and $u$ belongs to $N(u)$, hence $x$ is adjacent to exactly two vertices of $N(u)$.

Let $e$ be the number of edges whose endpoints both belong to $N(u)$.

We now count the nonedges inside $N(u)$.

Take two vertices $a,b\in N(u)$ that are not adjacent. Since $a$ and $b$ are strangers, they have exactly two common neighbors. One of them is $u$. Let $x$ be the other common neighbor. Since $x\ne u$ and $x$ is adjacent to both $a$ and $b$, the vertex $x$ does not belong to $N(u)$; otherwise $u,a,b$ would be three common neighbors of the adjacent pair $u,x$, contrary to the assumption that adjacent pairs have at most two common neighbors. Hence $x\in B$.

Conversely, each vertex $x\in B$ is adjacent to exactly two vertices of $N(u)$. Call them $a$ and $b$. These vertices cannot be adjacent, because then $u$ and $x$ would be two common neighbors of the adjacent pair $a,b$, and together with the edge endpoint relation this would give three common neighbors of $a$ and $b$, contradicting the bound of two. Thus $a$ and $b$ form a nonedge in $N(u)$.

The two constructions are inverse to each other. Therefore the number of nonedges in $N(u)$ equals $|B|$. Since the total number of pairs in $N(u)$ is $\binom m2$,

$$e=\binom m2-|B|.$$

For each $w\in N(u)$, let $c_w$ denote the number of common neighbors of $u$ and $w$. Since $u$ and $w$ are adjacent,

$$c_w\le2.$$

Every edge inside $N(u)$ contributes $1$ to $c_w$ for each of its two endpoints. Hence

$$\sum_{w\in N(u)} c_w =2e.$$

Using the formula for $e$,

$$\sum_{w\in N(u)} c_w =2\left(\binom m2-|B|\right) =m(m-1)-2|B|.$$

Next count incidences between vertices of $B$ and vertices of $N(u)$.

Each vertex of $B$ is adjacent to exactly two vertices of $N(u)$, so the number of incidences equals

$$2|B|.$$

For a fixed $w\in N(u)$, the number of neighbors of $w$ that lie in $B$ equals

$$\deg w-1-c_w,$$

because among the neighbors of $w$, one is $u$ and exactly $c_w$ lie in $N(u)$.

Therefore

$$2|B| =\sum_{w\in N(u)}(\deg w-1-c_w).$$

Substituting the expression for $\sum c_w$ gives

$$2|B| =\sum_{w\in N(u)}\deg w-m-\bigl(m(m-1)-2|B|\bigr).$$

After cancellation,

$$\sum_{w\in N(u)}\deg w=m^2.$$

Since $u$ has minimum degree $m$, every vertex $w\in N(u)$ satisfies

$$\deg w\ge m.$$

There are exactly $m$ such vertices, and their degrees sum to $m^2$. Hence each of them must satisfy

$$\deg w=m.$$

Thus every neighbor of $u$ has degree $m$.

Now take any vertex $x\in B$. The vertex $x$ is adjacent to exactly two vertices of $N(u)$; choose one of them and call it $w$. We have already proved that $\deg w=m$. Since $u$ has minimum degree $m$, the vertex $w$ also has minimum degree.

Applying the result already established to the minimum degree vertex $w$, every neighbor of $w$ has degree $m$. Since $x$ is a neighbor of $w$, it follows that

$$\deg x=m.$$

Every vertex of the graph is either $u$, a neighbor of $u$, or a vertex of $B$. All three kinds of vertices have degree $m$.

Hence every person knows exactly $m$ people.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the correspondence between nonedges inside $N(u)$ and vertices of $B$.

If $a,b\in N(u)$ are nonadjacent, then they have exactly two common neighbors. One is $u$. Let the other be $x$. The argument that $x\notin N(u)$ is essential. If $x$ were in $N(u)$, then the adjacent pair $u,x$ would have common neighbors $a$ and $b$, and also any additional common neighbor arising from the original configuration would violate the upper bound. The conclusion that $x\in B$ depends on excluding this possibility.

The second delicate point is the identity

$$2|B| =\sum_{w\in N(u)}(\deg w-1-c_w).$$

For each $w\in N(u)$, the neighbors of $w$ split into three disjoint classes: the vertex $u$, the $c_w$ common neighbors of $u$ and $w$, and the neighbors of $w$ in $B$. Counting the last class gives exactly $\deg w-1-c_w$. Omitting the subtraction of $c_w$ would count edges inside $N(u)$ incorrectly.

The third delicate point is the deduction from

$$\sum_{w\in N(u)}\deg w=m^2.$$

There are $m$ summands, and each is at least $m$. The smallest possible value of the sum is therefore $m^2$. Since the sum actually equals this minimum, every summand must equal $m$. Any weaker conclusion would leave open the possibility that some neighbor has degree larger than $m$, which would force another to have degree smaller than $m$, contradicting the minimality of $m$.

Alternative Approaches

A more graph theoretic proof uses the adjacency matrix. Let $A$ be the adjacency matrix and let $J$ be the all ones matrix. The hypotheses imply that for distinct vertices the number of common neighbors depends only on whether the vertices are adjacent. Translating this into matrix form yields a quadratic relation involving $A$, $J$, and a diagonal matrix of degrees. Comparing row sums shows that the degree vector is an eigenvector corresponding to a single eigenvalue, from which regularity follows.

The combinatorial proof above is preferable because it uses only elementary counting. The crucial identity $\sum_{w\in N(u)}\deg w=m^2$ emerges directly from the local conditions on common neighbors, and the conclusion follows immediately from the choice of a minimum degree vertex.