Kvant Math Problem 1168

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

Problem

There are 1989 cities and 4000 roads in a country (each road connects two cities). Prove that it is possible to choose a cyclic route passing through no more than 20 cities.

A. A. Razborov

Tournament of Towns (Autumn, 1988)

Exploration

Model the country by a graph with $1989$ vertices and $4000$ edges. A cyclic route corresponds to a cycle in the graph. The statement asks us to prove the existence of a cycle of length at most $20$.

A natural idea is to assume that every cycle is long and derive a contradiction from the number of edges. If the graph had no short cycles, then around any vertex the graph would look like a tree for many levels.

Let $g$ be the length of the shortest cycle. Suppose $g\ge 21$. Choose a vertex $v$. Consider all vertices at distance at most $10$ from $v$.

If two different vertices at level at most $9$ had a common neighbor in the next level, then the two shortest paths from $v$ to those vertices together with the common neighbor would create a cycle. The length of that cycle is at most

$$i+j+2,$$

where $i,j\le 9$, hence at most $20$, contradicting $g\ge21$.

Similarly, a vertex at level $i\le9$ cannot have two neighbors in the same previous level, because that would also create a cycle of length at most $2i\le18$.

Thus the ball of radius $10$ around $v$ is a tree.

A tree with levels $0,1,\dots,10$ contains exactly one more vertex than edges. Hence inside this ball the number of edges is at most the number of vertices minus $1$.

The crucial question is how to turn this local tree structure into a global bound on the total number of edges. A standard method is to delete vertices of degree $0$ or $1$. This process does not destroy cycles. After all such deletions, the remaining graph has minimum degree at least $2$ and still has girth at least $21$.

Now choose any vertex. Since every non-root vertex in the radius-$10$ tree has at least one edge leading to its parent and degree at least $2$, every vertex up to level $9$ has at least one child. Consequently the number of vertices in levels $0$ through $10$ is at least

$$1+2+2+\cdots+2=21.$$

This is far too weak.

A better count uses average degree. The graph has

$$\frac{2\cdot4000}{1989}>4$$

as average degree. Hence after repeatedly deleting vertices of degree at most $2$, one obtains a nonempty subgraph with minimum degree at least $3$. Indeed, every graph with average degree exceeding $2$ contains such a subgraph.

In a graph of girth at least $21$ and minimum degree at least $3$, the radius-$10$ ball around a vertex is a tree in which the root has at least $3$ children and every later vertex has at least $2$ children. Therefore it contains at least

$$1+3+3\cdot2+3\cdot2^2+\cdots+3\cdot2^9 =1+3(2^{10}-1) =3070$$

vertices.

Since the whole graph has only $1989$ vertices, this is impossible. Hence a cycle of length at most $20$ must exist.

The most delicate point is proving that the radius-$10$ ball is a tree when the girth is at least $21$.

Problem Understanding

We are given a graph with $1989$ vertices and $4000$ edges. We must prove that the graph contains a cycle passing through at most $20$ vertices.

This is a Type B problem. We must prove the stated existence claim.

The core difficulty is converting the large number of edges into a bound on the length of the shortest cycle. The intended mechanism is that a graph with many edges contains a subgraph of minimum degree at least $3$, while a graph whose shortest cycle has length at least $21$ must be extremely large if every vertex has degree at least $3$.

Proof Architecture

First, show that the graph contains a nonempty subgraph whose minimum degree is at least $3$; repeatedly delete vertices of degree at most $2$, and observe that such deletions cannot remove all vertices because the original average degree exceeds $4$.

Second, prove that in a graph of girth at least $21$, the ball of radius $10$ around any vertex is a tree; otherwise two distinct shortest paths from the center would create a cycle of length at most $20$.

Third, prove that in a graph with minimum degree at least $3$, each vertex in levels $1$ through $9$ of that tree has at least two children, while the root has at least three children.

Fourth, count the vertices in the radius-$10$ ball and obtain at least

$$1+3+3\cdot2+\cdots+3\cdot2^9=3070$$

vertices.

Finally, compare this with the total number $1989$ and derive a contradiction.

The lemma most likely to fail under scrutiny is the claim that the radius-$10$ ball is a tree, because one must verify carefully that any extra adjacency indeed yields a cycle of length at most $20$.

Solution

Assume, for contradiction, that every cycle in the graph has length at least $21$.

Let $G$ be the graph. Since $G$ has $1989$ vertices and $4000$ edges, its average degree equals

$$\frac{2\cdot4000}{1989}=\frac{8000}{1989}>4.$$

We claim that $G$ contains a nonempty subgraph $H$ whose minimum degree is at least $3$.

Starting from $G$, repeatedly delete any vertex whose degree is at most $2$, together with all incident edges. Suppose this process eventually deletes every vertex. Consider the graph just before a vertex is deleted. At that moment its degree is at most $2$. Summing these degrees over all deleted vertices shows that the total number of edges of the original graph is at most $2|V(G)|$. Hence

$$|E(G)|\le 2|V(G)|=3978,$$

contrary to $|E(G)|=4000$.

Thus the deletion process cannot remove all vertices. When it stops, the remaining graph $H$ is nonempty and every vertex of $H$ has degree at least $3$.

Since $H$ is a subgraph of $G$, every cycle of $H$ also has length at least $21$.

Choose any vertex $v$ of $H$. Let $L_i$ be the set of vertices at distance exactly $i$ from $v$.

We show that the subgraph induced by the vertices at distance at most $10$ from $v$ is a tree.

Take a vertex $x\in L_i$ with $1\le i\le10$. If $x$ had two neighbors in $L_{i-1}$, then the two shortest paths from $v$ to those neighbors, together with the edges joining them to $x$, would form a cycle of length at most

$$2i\le20,$$

contradicting our assumption.

Next, let $x,y\in L_i$ with $i\le9$, and suppose that $x$ and $y$ have a common neighbor $z\in L_{i+1}$. Each of $x$ and $y$ has a unique neighbor in $L_{i-1}$, hence unique shortest paths from $v$ to $x$ and $y$. Let $w$ be the last common vertex of these two paths. Then the union of the path from $w$ to $x$, the edges $xz$ and $zy$, and the path from $y$ back to $w$ forms a cycle. Its length is at most

$$(i-\ell)+(i-\ell)+2=2(i-\ell)+2\le 20,$$

where $\ell$ is the distance from $v$ to $w$. This is impossible.

Consequently every vertex of $L_i$ with $i\le9$ has distinct children in $L_{i+1}$, and each vertex of $L_{i+1}$ has exactly one parent in $L_i$. Hence the vertices at distances at most $10$ form a tree rooted at $v$.

Since every vertex of $H$ has degree at least $3$, the root $v$ has at least $3$ neighbors in $L_1$. Every vertex in $L_i$ for $1\le i\le9$ already uses one incident edge to its parent. Its degree is at least $3$, so it has at least two additional neighbors. None of these can lie in levels $0,\dots,i$, because such an edge would create a cycle of length at most $20$. Therefore each vertex in $L_i$ has at least two children in $L_{i+1}$.

Thus

$$|L_0|\ge1, \qquad |L_1|\ge3, \qquad |L_i|\ge3\cdot2^{,i-1}\quad (1\le i\le10).$$

Summing,

$$|V(H)| \ge 1+\sum_{i=1}^{10}3\cdot2^{i-1} = 1+3(2^{10}-1) = 3070.$$

But $H$ is a subgraph of $G$, and $G$ has only $1989$ vertices. This contradiction shows that our assumption was false.

Hence $G$ contains a cycle of length at most $20$. This completes the proof.

∎

Verification of Key Steps

The first delicate step is the existence of a subgraph of minimum degree at least $3$. If repeated deletion of vertices of degree at most $2$ removed all vertices, then every edge would be counted when its earlier endpoint was deleted. Since each deleted vertex contributes at most $2$ to this count, one obtains

$$|E(G)|\le 2|V(G)|.$$

For the given graph this would yield $|E(G)|\le3978$, contradicting $4000$.

The second delicate step is proving that the radius-$10$ ball is a tree. Suppose a vertex at level $i\le10$ had two parents in level $i-1$. Joining the two parent-to-root paths with the two parent edges produces a cycle of length at most $2i\le20$. Hence each vertex has at most one parent. Likewise, if two vertices at level $i\le9$ shared a child at level $i+1$, then the two root-to-parent paths together with the two child edges would create a cycle of length at most $2i+2\le20$. These are exactly the configurations that would destroy the tree structure.

The third delicate step is the growth estimate. A vertex in level $i\le9$ has degree at least $3$. One incident edge goes to its parent. Any additional edge to its own level or an earlier level would create a cycle entirely inside the radius-$10$ ball, whose length would not exceed $20$. Hence at least two incident edges must go to new vertices in level $i+1$. This justifies the doubling factor.

Alternative Approaches

One may invoke the Moore bound directly. A graph of minimum degree at least $3$ and girth at least $21$ must contain at least

$$1+3+3\cdot2+\cdots+3\cdot2^9=3070$$

vertices. After extracting a subgraph of minimum degree at least $3$, the contradiction with $1989$ vertices is immediate.

The presented proof is preferable because it derives the relevant Moore bound from first principles. Every ingredient is elementary: pruning low-degree vertices, proving the radius-$10$ neighborhood is a tree, and counting vertices level by level.