Kvant Math Problem 250

Represent friendship by a graph $G$ whose vertices are the knights, with an edge joining two friends.

kvantmathematicsolympiad

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

Problem

  1. At the court of King Arthur, $n$ knights have gathered. Some of them are enemies of one another, but each knight has at least $\dfrac{n}{2}$ friends among those present. Prove that Merlin, King Arthur’s adviser, can seat the knights around a round table so that each knight is seated next to his friends.
  2. Prove that if each knight has an even (and, of course, positive) number of friends, then Merlin can seat the knights at several round tables so that no one sits next to an enemy (Arthur has tables for two, three, and more people).

V. N. Vaguten

Exploration

Represent friendship by a graph $G$ whose vertices are the knights, with an edge joining two friends. The first statement says that every vertex has degree at least $n/2$. We must arrange the vertices on a cycle so that consecutive vertices are adjacent. In graph language, we must prove that $G$ contains a Hamiltonian cycle.

This immediately suggests Dirac's theorem: a graph on $n\ge 3$ vertices with minimum degree at least $n/2$ is Hamiltonian. Since the problem predates many modern expositions, it is natural to reprove exactly the special case needed.

A standard proof starts from a longest path

$$v_1v_2\cdots v_k.$$

Because the path is maximal, every neighbor of $v_1$ and every neighbor of $v_k$ lies on the path. Since both degrees are at least $n/2$, there are many indices along the path. One then shows that there exists $i$ such that

$$v_1v_{i+1}\in E,\qquad v_iv_k\in E.$$

These two extra edges close the path into a cycle containing all vertices of the path. If $k<n$, a vertex outside the cycle must have a neighbor on it, which enlarges the path, contradicting maximality. Hence $k=n$.

The delicate point is proving the existence of the index $i$. The usual counting argument is that the sets

$$A={i: v_i\text{ adjacent to }v_k}, \qquad B={i: v_{i+1}\text{ adjacent to }v_1}$$

are subsets of ${1,\dots,k-1}$ whose sizes sum to at least $n$. Since $k\le n$, they cannot be disjoint.

For the second statement, every vertex has positive even degree. A graph all of whose vertices have even degree decomposes into edge-disjoint cycles. Since degrees are positive, every vertex belongs to at least one cycle. Seating the knights around each cycle gives the desired arrangement. The only thing to check is that the cycles can be chosen vertex-disjoint and covering all vertices. This follows by taking connected components separately and using Eulerian circuits. Traversing an Eulerian circuit and deleting repeated visits produces a decomposition into edge-disjoint simple cycles. Equivalently, repeatedly remove a cycle from an even graph; parity is preserved.

The first part is the harder one. The counting step in the Hamiltonicity proof is the place where an incorrect argument is most likely.

Problem Understanding

We model friendship by an undirected graph. Vertices represent knights and an edge joins two knights exactly when they are friends.

In the first part, every vertex has degree at least $n/2$. We must prove that the vertices can be arranged around one round table so that neighboring seats correspond to friendship. Graph-theoretically, we must prove that the friendship graph contains a Hamiltonian cycle.

In the second part, every vertex has a positive even degree. We must prove that the knights can be partitioned among several round tables so that neighboring knights at each table are friends. Graph-theoretically, we must partition the vertex set into cycles.

This is a Type B problem. The task is to prove the stated existence claims.

The core difficulty is the first part, namely showing that the minimum-degree condition forces a Hamiltonian cycle.

Proof Architecture

Lemma 1. A longest path in a graph of minimum degree at least $n/2$ can be converted into a cycle containing all vertices of the path.

Sketch. Count the neighbors of the two endpoints along the path and show that two suitable chords must exist.

Lemma 2. In a graph of minimum degree at least $n/2$, a cycle containing all vertices of a longest path must contain every vertex of the graph.

Sketch. If some vertex were outside the cycle, it would have a neighbor on the cycle; breaking the cycle at that neighbor would produce a longer path.

Lemma 3. Every finite graph whose vertices all have even degree can be decomposed into vertex-disjoint cycles covering all vertices.

Sketch. Each connected component is Eulerian. Repeatedly remove a cycle; parity is preserved until no edges remain.

The hardest part is Lemma 1, specifically the counting argument guaranteeing the existence of the two crossing chords.

Solution

Let $G$ be the friendship graph.

Part 1

Assume every vertex of $G$ has degree at least $n/2$.

Take a path of maximum possible length,

$$P=v_1v_2\cdots v_k.$$

Since $P$ is maximal, every neighbor of $v_1$ and every neighbor of $v_k$ lies among the vertices of $P$; otherwise the path could be extended.

Define

$$A={,i\in{1,\dots ,k-1}: v_i\text{ is adjacent to }v_k,},$$

and

$$B={,i\in{1,\dots ,k-1}: v_{i+1}\text{ is adjacent to }v_1,}.$$

Because all neighbors of $v_k$ lie on the path,

$$|A|=\deg(v_k)\ge \frac n2.$$

Similarly,

$$|B|=\deg(v_1)\ge \frac n2.$$

The sets $A$ and $B$ are contained in ${1,\dots,k-1}$, which has $k-1$ elements. Since $k\le n$,

$$|A|+|B| \ge n > k-1.$$

Hence $A$ and $B$ cannot be disjoint. Choose

$$i\in A\cap B.$$

Then

$$v_iv_k\in E, \qquad v_1v_{i+1}\in E.$$

Using these edges, form the cycle

$$v_1,v_2,\dots,v_i,v_k,v_{k-1},\dots,v_{i+1},v_1.$$

This cycle contains exactly the vertices of the path $P$.

We claim that this cycle contains all vertices of $G$.

Suppose not. Let $u$ be a vertex outside the cycle. Since every vertex has degree at least $n/2>0$, the vertex $u$ has a neighbor. If every neighbor of $u$ were also outside the cycle, then the component containing $u$ would contain at most $n-k$ vertices. Consequently

$$\deg(u)\le n-k-1.$$

Since $k\ge n/2+1$ because the path contains $v_1$ together with all at least $n/2$ neighbors of $v_1$,

$$n-k-1<\frac n2,$$

contradicting $\deg(u)\ge n/2$.

Therefore $u$ has a neighbor on the cycle. Let that neighbor be $w$.

Delete from the cycle one of the two cycle edges incident with $w$. The remaining edges form a path containing all $k$ vertices of the cycle and having $w$ as an endpoint. Adding the edge $uw$ extends this path to a path with $k+1$ vertices.

This contradicts the maximality of $P$.

Hence no vertex lies outside the cycle. The cycle contains all $n$ vertices, so it is a Hamiltonian cycle. Seating the knights around one round table in the order given by this cycle places every knight between two friends.

Part 2

Assume now that every knight has a positive even number of friends. Equivalently, every vertex of $G$ has positive even degree.

Consider any connected component of $G$. Every vertex in this component has even degree, so the component is Eulerian. Therefore it contains a closed trail using every edge exactly once.

A connected Eulerian graph contains a cycle. Remove the edges of one such cycle. Every remaining vertex still has even degree, because removing a cycle decreases the degree of each vertex on that cycle by $2$ and leaves all other degrees unchanged.

If edges remain, the same argument yields another cycle. Repeating this process finitely many times decomposes the component into edge-disjoint cycles.

Since every vertex originally had positive degree, every vertex is incident with some edge and hence belongs to at least one of the cycles in the decomposition.

Whenever two cycles share a vertex, their union contains a larger closed walk. Splitting that closed walk into simple cycles yields a cycle decomposition in which the number of shared vertices decreases. Repeating this operation produces a decomposition into vertex-disjoint cycles covering all vertices of the component.

Applying this to every connected component, the whole vertex set is partitioned into vertex-disjoint cycles.

Seat the knights of each cycle around one round table in cyclic order. Consecutive knights on a table are joined by an edge of the friendship graph, hence are friends. No knight sits next to an enemy.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the proof that $A\cap B\neq\varnothing$.

The sets $A$ and $B$ both lie in ${1,\dots,k-1}$. Their sizes satisfy

$$|A|\ge \frac n2,\qquad |B|\ge \frac n2.$$

Hence

$$|A|+|B|\ge n.$$

Since $k\le n$,

$$k-1<n.$$

A disjoint union of subsets of a set with $k-1$ elements cannot have at least $n$ elements. Thus $A$ and $B$ must intersect. Omitting the strict inequality $k-1<n$ would leave a gap.

The second delicate step is showing that a vertex outside the cycle must have a neighbor on the cycle.

If all neighbors of $u$ were outside, then

$$\deg(u)\le n-k-1.$$

A longest path contains at least $n/2+1$ vertices because one endpoint has at least $n/2$ neighbors and all of them lie on the path. Hence

$$n-k-1\le n-\left(\frac n2+1\right)-1 =\frac n2-2<\frac n2,$$

contradicting the minimum-degree condition.

The third delicate step is the cycle decomposition in Part 2.

Removing the edges of a cycle changes every degree by either $0$ or $2$, so parity remains even. Thus another cycle exists whenever edges remain. Since the graph is finite, the process terminates. Every original vertex has positive degree, so it is incident with at least one removed cycle and is covered.

Alternative Approaches

For the first part one may invoke the classical theorem of Gabriel Dirac: every graph on $n\ge3$ vertices with minimum degree at least $n/2$ is Hamiltonian. The proof given above is essentially Dirac's original argument specialized to this problem and avoids importing the theorem as a black box.

For the second part one may work directly with Eulerian circuits. In each connected component, traverse an Eulerian circuit. Whenever a vertex is encountered for the second time, cut the circuit at the two occurrences. Repeating this operation decomposes the Eulerian circuit into simple cycles whose vertex sets are disjoint and cover all vertices of the component. Seating the knights along these cycles immediately yields the required arrangement.