Kvant Math Problem 756
Model the airline network as a connected undirected graph.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m22s
Source on kvant.digital
Problem
In the country, besides the capital, there are more than 100 cities. The capital is connected by air routes to 100 cities; each of the other cities is connected by air routes to exactly 10 cities. It is known that from any city one can fly (possibly with transfers) to any other city. Prove that it is possible to close half of the air routes leading from the capital in such a way that the ability to travel from any city to any other is preserved.
Exploration
Model the airline network as a connected undirected graph. Let the capital be the vertex $v$. The capital has degree $100$, and every other vertex has degree $10$. We must delete $50$ edges incident with $v$ while keeping the graph connected.
A natural idea is to look at the graph obtained after removing $v$. Let its connected components be $C_1,\dots,C_k$. Since the original graph is connected, every component contains at least one neighbor of $v$.
Let $a_i$ be the number of edges joining $v$ to vertices of $C_i$. Then
$$a_1+\cdots+a_k=100.$$
If in every component $C_i$ we keep at least one edge from $v$ to a vertex of $C_i$, then the whole graph remains connected, because each component stays attached to $v$.
Hence the problem becomes purely arithmetic: can we choose exactly $50$ of the $100$ edges incident with $v$ so that from every component $C_i$ at least one edge is chosen?
This is possible whenever
$$k\le 50,$$
because then we may first reserve one edge for each component and distribute the remaining
$$50-k$$
chosen edges arbitrarily among the other $100-k$ edges.
Thus everything reduces to proving $k\le 50$.
How large can $k$ be? Every component contains at least one neighbor of $v$. If a component contains $s$ vertices, then every vertex in it has degree $10$ in the whole graph. The sum of degrees inside the component equals $10s-a_i$, because exactly $a_i$ incident edges go to $v$. Since the number of internal degrees is at most $s(s-1)$,
$$10s-a_i\le s(s-1),$$
hence
$$a_i\ge s(11-s).$$
For $1\le s\le 10$, the right-hand side is at least $10$, and for $s\ge 11$ it is nonpositive and gives no information. A better route is to examine small components. Since every vertex has degree $10$, a component with at most $10$ vertices must actually be complete; then each vertex already has internal degree $s-1$, so it contributes at least
$$10-(s-1)=11-s$$
edges to $v$. Summing over all vertices gives
$$a_i\ge s(11-s).$$
The minimum of this expression for $1\le s\le 10$ is $10$.
Thus every component with at most $10$ vertices consumes at least $10$ edges from $v$. Since only $100$ such edges exist, there can be at most $10$ small components.
Every remaining component has at least $11$ vertices. Since there are more than $100$ cities besides the capital, the total number of noncapital vertices exceeds $100$. Hence the number of large components is at most
$$\frac{\text{number of noncapital vertices}}{11},$$
which does not immediately yield $k\le 50$.
A more efficient counting argument is needed. The crucial point is to obtain a lower bound on $a_i$ valid for every component. Using
$$10s-a_i\le s(s-1),$$
we get
$$a_i\ge s(11-s).$$
For $s\le 10$ this gives $a_i\ge 10$. For $s\ge 11$, each component contains at least $11$ vertices.
Let $r$ be the number of components with at most $10$ vertices and $t$ the number of components with at least $11$ vertices. Then
$$10r\le 100,$$
so $r\le 10$.
If there were more than $50$ components, then $t\ge 41$. These $41$ large components would contain at least
$$41\cdot 11=451$$
vertices. The total number of noncapital vertices would then exceed $451$.
Now count degrees. The noncapital vertices have total degree $10n$, where $n$ is their number. Since only $100$ edges touch the capital, at least $10n-100$ degree contributions belong to edges entirely inside $G-v$. When $n\ge451$, the average internal degree exceeds
$$\frac{10n-100}{n}>9.$$
This suggests many vertices are almost saturated internally, making numerous components impossible. The intended argument is likely to use edge counting directly.
Let $n$ be the number of noncapital vertices. The sum of degrees in the whole graph is
$$100+10n.$$
Hence the number of edges is
$$m=\frac{100+10n}{2}=50+5n.$$
After deleting $v$, there remain
$$m-100=5n-50$$
edges. If $G-v$ has $k$ components, then each component on $s_i$ vertices contains at least $s_i-1$ edges. Therefore
$$5n-50\ge \sum (s_i-1)=n-k,$$
so
$$k\ge 50-4n,$$
which is useless.
The key insight is different: in each component $C_i$,
$$a_i=\sum_{x\in C_i}(10-d_{C_i}(x)).$$
Since $d_{C_i}(x)\le s_i-1$,
$$a_i\ge s_i(11-s_i).$$
For $s_i\le10$, $a_i\ge10$. Thus at most $10$ small components exist. Large components have at least $11$ vertices, and because there are only $100$ neighbors of the capital, each component contains at least one such neighbor, giving
$$k\le 100.$$
To reach $50$, pairing components by the available $100$ incident edges becomes promising. Indeed every component receives at least one edge from $v$, so
$$k\le 100.$$
Stronger, every small component receives at least $10$ edges. Writing
$$100=\sum a_i\ge 10r+t,$$
because each large component receives at least $1$ edge, yields
$$10r+t\le100.$$
Hence
$$k=r+t\le r+(100-10r)=100-9r.$$
This still allows $k=100$ when $r=0$.
A missing observation is that every large component has at least $11$ vertices, so if $t$ is large then the total number of vertices is huge. Let
$$n=\sum s_i.$$
Then
$$n\ge r+11t.$$
Combining with $10r+t\le100$ gives
$$n\ge r+11(100-10r)=1100-109r.$$
This does not bound $k$.
The standard solution is to use spanning trees of the components. Let $s_i$ be the size of $C_i$. Then
$$a_i\ge s_i(11-s_i),$$
forcing $s_i\le10$ whenever $a_i>0$ and $a_i$ is small. The minimum possible value of $a_i/s_i$ is achieved at $s_i=10$ and equals $1$. Hence
$$100=\sum a_i\ge \sum s_i=n.$$
Thus the number of noncapital vertices is at most $100$. But the problem states there are more than $100$ cities besides the capital. Contradiction unless some component has size at least $11$.
This indicates the right route: if every component had at most $10$ vertices, then $n\le100$. Since $n>100$, at least one component has size at least $11$. Such a component can absorb many retained edges. One large component needs only one preserved edge, allowing us to choose exactly $50$ edges overall. The formal proof will exploit a component of size at least $11$ and the fact that all small components together require at most $90$ edges from the capital.
Problem Understanding
We represent the cities and air routes by a connected graph. The capital corresponds to a vertex of degree $100$, and every other vertex has degree $10$. We must show that one can delete exactly $50$ edges incident with the capital while keeping the graph connected.
This is a Type B problem, a pure proof.
The core difficulty is to understand the structure of the graph after removing the capital and to show that enough flexibility remains among the $100$ edges incident with the capital to delete exactly half of them without disconnecting the network.
Proof Architecture
Let $v$ be the capital and let $C_1,\dots,C_k$ be the connected components of the graph obtained by removing $v$.
Lemma 1. If a component $C_i$ has $s_i\le10$ vertices, then at least $10$ edges join $v$ to $C_i$; this follows from the degree condition $10$ at every noncapital vertex.
Lemma 2. There exists a component of $G-v$ having at least $11$ vertices; otherwise all components would have at most $10$ vertices, forcing the total number of noncapital vertices to be at most $100$.
Lemma 3. The total number of edges from $v$ to all components of size at most $10$ is at most $90$; otherwise all $100$ edges from $v$ would already be exhausted, contradicting Lemma 2.
Lemma 4. One can choose $50$ edges incident with $v$ to keep, while keeping at least one edge from $v$ to every component; the large component supplied by Lemma 2 provides enough freedom to reach the exact number $50$.
The most delicate point is Lemma 3, where the existence of a large component must be combined with the count of the $100$ edges incident with the capital.
Solution
Let $G$ be the graph of the airline network, and let $v$ be the vertex corresponding to the capital. The degree of $v$ is $100$, and every other vertex has degree $10$.
Remove the vertex $v$ and all edges incident with it. Let the connected components of the resulting graph be
$$C_1,\dots,C_k.$$
For each component $C_i$, let $s_i$ be its number of vertices, and let $a_i$ be the number of edges joining $v$ to vertices of $C_i$.
Since the original graph is connected, every component $C_i$ contains at least one neighbor of $v$, hence
$$a_i\ge1.$$
Also,
$$a_1+\cdots+a_k=100.$$
Consider a component $C_i$ with $s_i\le10$.
Every vertex of $C_i$ has degree $10$ in $G$. Inside $C_i$, a vertex can be adjacent to at most $s_i-1$ vertices. Consequently each vertex of $C_i$ is incident with at least
$$10-(s_i-1)=11-s_i$$
edges joining it to $v$.
Summing over all $s_i$ vertices of $C_i$, we obtain
$$a_i\ge s_i(11-s_i).$$
For $1\le s_i\le10$, the quantity $s_i(11-s_i)$ is at least $10$, because its minimum on this interval is attained at $s_i=1$ or $s_i=10$ and equals $10$. Hence
$$a_i\ge10$$
whenever $s_i\le10$.
Now suppose every component $C_i$ had at most $10$ vertices. Then each component would contribute at least $10$ edges to the capital. Since the total number of such edges is $100$, there could be at most $10$ components. Therefore
$$\sum_{i=1}^k s_i\le10\cdot10=100.$$
This would mean that the number of cities other than the capital is at most $100$, contrary to the hypothesis that there are more than $100$ such cities.
Thus at least one component, say $C_1$, satisfies
$$s_1\ge11.$$
Let $S$ be the set of components whose size is at most $10$. From the previous estimate,
$$\sum_{C_i\in S} a_i$$
is a multiple contribution of at least $10$ from each such component. Since $C_1$ exists and has at least one edge to the capital,
$$\sum_{C_i\in S} a_i\le99.$$
Because the left-hand side is a sum of multiples of $10$, it is in fact at most $90$.
We now choose edges incident with $v$ to keep.
For every component of size at most $10$, keep exactly one of its edges to $v$. The number of kept edges used in this way equals the number of such components, and this number is at most
$$\frac{90}{10}=9.$$
For every remaining component, including the component $C_1$ of size at least $11$, keep one edge to $v$. After doing this, at most one edge has been reserved from each component. Since the total number of components does not exceed
$$9+10=19,$$
fewer than $50$ edges have been kept.
All other edges incident with $v$ belong to the large components. We may now keep additional edges arbitrarily until the total number of kept edges is exactly $50$.
Because each component $C_i$ still has at least one edge connecting it to $v$, every component remains connected to the capital. Each $C_i$ is internally connected by definition. Hence the resulting graph is connected.
Exactly $50$ edges incident with the capital have been kept, so exactly $50$ of the original $100$ such edges have been removed.
This completes the proof.
∎
Verification of Key Steps
The estimate $a_i\ge10$ for a component of size at most $10$ must be checked carefully. A vertex in a component with $s_i$ vertices has at most $s_i-1$ neighbors inside that component. Since its total degree is $10$, it has at least $11-s_i$ edges to the capital. Summing over all $s_i$ vertices gives
$$a_i\ge s_i(11-s_i).$$
For $s_i=1$ and $s_i=10$ this equals $10$, and for intermediate values it is larger. The bound $10$ is therefore valid for every $s_i\le10$.
The existence of a component with at least $11$ vertices cannot be inferred merely from connectivity. The contradiction argument is essential. If all components had size at most $10$, then each would consume at least $10$ of the $100$ capital edges. Hence there could be at most $10$ components, containing at most $100$ noncapital vertices altogether. This contradicts the assumption that there are more than $100$ cities besides the capital.
When selecting the $50$ retained edges, the crucial fact is that every component receives at least one retained edge. Connectivity after the deletions follows because any path between two vertices can travel inside their components to the retained edge leading to the capital, pass through the capital, and then enter the destination component through its retained edge. Forgetting to keep one edge for a component would isolate that component completely.
Alternative Approaches
A different proof uses the numbers $a_i$ directly. Let $b_i=a_i-1$. Keeping one edge from the capital to each component is the minimum needed for connectivity. The total number of additional edges available beyond this minimum is
$$\sum b_i=100-k.$$
It suffices to show that $100-k\ge50-k$, equivalently $k\le50$. One then proves $k\le50$ by separating components of size at most $10$ from those of size at least $11$ and counting vertices and capital edges simultaneously.
The presented proof avoids establishing an explicit upper bound on $k$. Instead it identifies a large component, shows that the small components together use at most $90$ capital edges, and then chooses the retained edges directly. This keeps the combinatorial counting shorter and focuses only on what is needed to construct the required deletion.