Kvant Math Problem 188
Represent the airline network by a simple graph $G$ on $2n$ vertices.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m32s
Source on kvant.digital
Problem
Air service has been established between some of $2n$ cities, and each city is connected to at least $n$ others (by non-stop flights). Prove that even if any $n-1$ flights are canceled, it will still be possible to travel by air (with transfers) from any city to any other. Determine all cases in which this “connectivity” is destroyed when $n$ flights are canceled.
A. K. Kelmans
Exploration
Represent the airline network by a simple graph $G$ on $2n$ vertices. Two cities are adjacent when there is a non-stop flight between them. The condition says that every vertex has degree at least $n$.
The first statement asks for a lower bound on edge connectivity. A natural conjecture is that every cut separating the graph into two nonempty parts contains at least $n$ edges. If that is true, removing fewer than $n$ edges cannot disconnect the graph.
Take a partition $V(G)=A\cup B$, with $|A|=a$, $|B|=b$, $a+b=2n$. Suppose there are no edges between $A$ and $B$. Then a vertex of $A$ has degree at most $a-1$, so $a-1\ge n$. Likewise $b-1\ge n$. Since $a+b=2n$, this is impossible. Hence the graph is connected.
To estimate a cut, assume $a\le b$. Then $a\le n$. Every vertex of $A$ has at most $a-1$ neighbors inside $A$, hence at least
$$n-(a-1)=n-a+1$$
neighbors in $B$. Summing over vertices of $A$, the cut contains at least
$$a(n-a+1)$$
edges.
The minimum of $a(n-a+1)$ for $1\le a\le n$ must be examined. Testing:
$$a=1 \implies n,\qquad a=2 \implies 2(n-1),$$
and for $a=n$ the value is $n$. Since the quadratic is concave, its minimum on the interval occurs at an endpoint, giving at least $n$ edges. Thus every edge cut has size at least $n$.
Now determine when a cut of size exactly $n$ exists. We need equality in
$$a(n-a+1)\ge n.$$
For $1<a<n$, one has
$$a(n-a+1)>n,$$
so equality requires $a=1$ or $a=n$.
If $a=1$, the cut consists of all edges incident with a vertex of degree exactly $n$. Removing those $n$ edges isolates that vertex.
If $a=n$, then equality in the estimate forces every vertex of $A$ to have exactly one neighbor in $B$, and degree exactly $n$. Since the cut has $n$ edges and each vertex of $A$ contributes one cut edge, each vertex of $B$ must also contribute one cut edge. Hence the cut edges form a perfect matching between two sets of $n$ vertices. Removing those $n$ matching edges separates the graph into two components of size $n$.
The crucial point is proving that these are the only possibilities when a cut has size exactly $n$.
Problem Understanding
We are given a graph on $2n$ vertices whose minimum degree is at least $n$. We must prove that deleting any $n-1$ edges leaves the graph connected. Then we must classify all situations in which deleting exactly $n$ edges can disconnect the graph.
This is a Type A problem. We must determine all configurations in which connectivity can be destroyed by removing $n$ edges, prove that each such configuration indeed works, and prove that no other configuration is possible.
The core difficulty is the classification of minimum edge cuts. The degree condition forces every edge cut to contain at least $n$ edges, and equality can occur only in very special circumstances.
Proof Architecture
Lemma 1. For every partition $V(G)=A\cup B$ with $A,B\neq\varnothing$ and $|A|=a\le b=|B|$, the number of edges joining $A$ and $B$ is at least $a(n-a+1)$; this follows from the minimum degree condition.
Lemma 2. Every edge cut contains at least $n$ edges; this follows by minimizing $a(n-a+1)$ over $1\le a\le n$.
Lemma 3. Deleting any $n-1$ edges cannot disconnect the graph; otherwise the deleted edges would contain an edge cut of size at most $n-1$.
Lemma 4. If an edge cut has exactly $n$ edges, then either one side consists of a single vertex of degree $n$, or both sides have size $n$ and the cut edges form a perfect matching; this follows from the equality cases in Lemma 1.
The hardest direction is Lemma 4, because every equality condition must be extracted carefully from the lower bound.
Solution
Let $G$ be the graph whose vertices are the $2n$ cities and whose edges are the flights. Every vertex has degree at least $n$.
Consider an arbitrary partition
$$V(G)=A\cup B,$$
where $A,B\neq\varnothing$, and write
$$|A|=a,\qquad |B|=b,\qquad a+b=2n.$$
Assume $a\le b$, so $a\le n$.
Let $m(A,B)$ denote the number of edges joining $A$ and $B$. A vertex of $A$ has at most $a-1$ neighbors inside $A$. Since its degree is at least $n$, it has at least
$$n-(a-1)=n-a+1$$
neighbors in $B$.
Summing over all vertices of $A$, each edge joining $A$ and $B$ is counted exactly once. Hence
$$m(A,B)\ge a(n-a+1).$$
Since $1\le a\le n$, we examine the function
$$f(a)=a(n-a+1).$$
It is a concave quadratic. Therefore its minimum on the interval $[1,n]$ is attained at an endpoint. Since
$$f(1)=n,\qquad f(n)=n,$$
we obtain
$$m(A,B)\ge n.$$
Thus every edge cut contains at least $n$ edges.
Suppose now that fewer than $n$ edges are removed. If the resulting graph were disconnected, the removed set would contain all edges of some edge cut. That cut would have fewer than $n$ edges, contradicting the previous paragraph. Hence deleting any $n-1$ edges leaves the graph connected.
It remains to determine when deleting exactly $n$ edges can disconnect the graph.
Assume that a set of $n$ edges is removed and the graph becomes disconnected. Then the removed edges contain an edge cut. Since every edge cut has at least $n$ edges, that cut must contain exactly $n$ edges.
Let $V(G)=A\cup B$ be the corresponding partition, with $a=|A|\le |B|$. Then
$$m(A,B)=n.$$
Since
$$m(A,B)\ge a(n-a+1),$$
we have
$$a(n-a+1)\le n.$$
For $1<a<n$,
$$a(n-a+1)-n=(a-1)(n-a)>0,$$
so
$$a(n-a+1)>n.$$
Therefore equality is possible only when
$$a=1 \quad\text{or}\quad a=n.$$
First case: $a=1$.
Let $A={v}$. Since the cut has exactly $n$ edges,
$$\deg(v)=n.$$
The cut consists of all edges incident with $v$. Removing these $n$ edges isolates $v$, so the graph becomes disconnected.
Second case: $a=n$.
Now $|A|=|B|=n$. Since
$$m(A,B)=a(n-a+1)=n,$$
equality holds in the estimate obtained by summing the lower bounds for vertices of $A$. Hence every vertex of $A$ has exactly
$$n-a+1=1$$
neighbor in $B$ and degree exactly $n$.
There are $n$ vertices in $A$ and exactly $n$ cut edges. Since each vertex of $A$ is incident with one cut edge, every cut edge is accounted for. Consequently each vertex of $B$ is incident with at most one cut edge. The total number of cut edges is $n$, and there are $n$ vertices in $B$, so each vertex of $B$ is incident with exactly one cut edge.
Hence the cut edges form a perfect matching between $A$ and $B$. Removing these $n$ matching edges disconnects the graph into the two induced subgraphs on $A$ and $B$.
We have shown that every disconnecting set of $n$ edges arises in one of these two ways, and each of these two constructions indeed disconnects the graph.
Therefore the only cases in which connectivity is destroyed by deleting $n$ edges are:
- All $n$ edges incident with a vertex of degree exactly $n$ are deleted.
- The vertices split into two sets of $n$ vertices each, every vertex has exactly one neighbor in the other set, and the $n$ cross edges, which form a perfect matching, are deleted.
$$\boxed{\text{Exactly the two cases described above.}}$$
Verification of Key Steps
The first delicate step is the estimate
$$m(A,B)\ge a(n-a+1).$$
For a vertex of $A$, at most $a-1$ incident edges stay inside $A$. Since its degree is at least $n$, at least $n-a+1$ incident edges cross to $B$. Summing over all vertices of $A$ counts every crossing edge exactly once. No edge is omitted and none is counted twice.
The second delicate step is identifying when
$$a(n-a+1)=n.$$
Direct computation gives
$$a(n-a+1)-n=(a-1)(n-a).$$
For $1<a<n$ both factors are positive, so the difference is positive. Equality occurs only at the endpoints $a=1$ and $a=n$.
The third delicate step is proving that in the case $a=n$ the cut edges form a perfect matching. Equality in the lower bound implies every vertex of $A$ has exactly one neighbor in $B$. Since there are $n$ vertices in $A$, this already accounts for all $n$ cut edges. If some vertex of $B$ were incident with two cut edges, another vertex of $B$ would be incident with none, and the total number of incidences on the $B$ side would still be $n$; however a vertex of $B$ with no cut edge would have all neighbors in $B$, forcing degree at most $n-1$, contradicting the minimum degree condition. Thus every vertex of $B$ has exactly one cut edge, and the cut is a perfect matching.
Alternative Approaches
The result can also be viewed as a special case of edge connectivity bounds. A classical theorem states that a graph on $N$ vertices with minimum degree at least $N/2$ is maximally edge connected, meaning its edge connectivity equals its minimum degree. Here $N=2n$, so every edge cut has size at least $n$. The first part then follows immediately.
For the classification of cuts of size $n$, one may start from the equality case in the edge connectivity bound. Such proofs usually show that a minimum cut separates either a single minimum degree vertex or two equal halves joined by a perfect matching. The direct counting argument used above is preferable here because it derives the classification from the same inequality that proves the connectivity statement, without invoking any external theorem.