Kvant Math Problem 412
Model the city as a finite directed graph $G=(V,E)$ in which vertices are squares and directed edges are one-way streets.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m18s
Source on kvant.digital
Problem
In a city, each square has at least three streets leading out of it. One-way traffic has been established on all streets in such a way that it is possible to drive from any square to any other square. Prove that it is possible to prohibit traffic on one of the streets (on the segment between two squares) in such a way that it will still be possible to drive from any square to any other square.
A. Goldberg
Exploration
Model the city as a finite directed graph $G=(V,E)$ in which vertices are squares and directed edges are one-way streets. The condition that one can drive from any square to any other square means that $G$ is strongly connected.
Each square has at least three streets leading out of it in the underlying undirected sense, so every vertex has degree at least $3$ in the underlying simple graph. After orientation, this implies that each vertex has total incident directed edges at least $3$, though the split between in-degree and out-degree is not fixed.
We are asked to prove the existence of a directed edge whose removal preserves strong connectivity. In graph-theoretic language, we must show that there exists an arc that is not a strong bridge.
A natural obstruction is a directed cycle: in a directed cycle, removing any edge destroys strong connectivity. However, in a directed cycle every vertex has degree $2$ in the underlying graph, contradicting the assumption of degree at least $3$. Thus the graph is strictly more complex than a single cycle, suggesting the existence of redundant directed paths around at least one edge.
The key point is to understand what structure forces every edge to be essential. If every edge were a strong bridge, then removing any one would break strong connectivity. This rigidity should force extreme degree constraints, plausibly reducing the graph to a directed cycle, which contradicts the degree condition.
The main difficulty is to turn the informal idea “an edge is essential only if no detour exists” into a structural restriction strong enough to force a contradiction.
Problem Understanding
This is a Type A problem. We must prove that there exists at least one directed edge whose removal does not destroy strong connectivity.
Equivalently, in a strongly connected directed graph whose underlying undirected minimum degree is at least $3$, we must show that not all edges are strong bridges.
The core difficulty is excluding the degenerate case in which every edge is indispensable. The expected mechanism is that such rigidity forces each vertex to have exactly one incoming and one outgoing edge, producing a directed cycle, which contradicts the given degree condition.
Proof Architecture
First, we introduce the notion of a strong bridge, an edge whose removal destroys strong connectivity.
Next, we prove that if every edge is a strong bridge, then every vertex must have out-degree exactly $1$, since otherwise two distinct outgoing edges would create redundancy contradicting their essentiality.
We then prove similarly that every vertex must have in-degree exactly $1$.
From these two facts, we deduce that the directed graph is a disjoint union of directed cycles, and strong connectivity forces it to be a single directed cycle.
Finally, we observe that a directed cycle has underlying undirected degree $2$ at every vertex, contradicting the assumption that every vertex has degree at least $3$. Hence not every edge can be a strong bridge, so at least one edge is removable while preserving strong connectivity.
The hardest step is proving that out-degree at least $2$ at a vertex forces the existence of a non-bridge edge.
Solution
Call a directed edge a strong bridge if removing it destroys strong connectivity. Assume for contradiction that every edge is a strong bridge.
Fix a vertex $v$ and suppose it has two distinct outgoing edges $v \to a$ and $v \to b$. Since the graph is strongly connected, there exists a directed path from $a$ to $b$. Consider such a path and write it as
$$a \to x_1 \to x_2 \to \cdots \to x_k \to b.$$
This path together with the edge $v \to a$ gives a directed walk from $v$ to $b$ that does not use the edge $v \to b$.
Now consider the graph after removing the edge $v \to b$. We show that strong connectivity is preserved, contradicting the assumption that $v \to b$ is a strong bridge. Indeed, for any vertex $y$, any directed path from $b$ to $y$ in the original graph remains valid after removing $v \to b$ unless it uses this edge. If it uses $v \to b$, we replace the segment $v \to b$ by the alternative route
$$v \to a \to x_1 \to \cdots \to x_k \to b,$$
which avoids the removed edge. Hence every path involving $v \to b$ can be rerouted, so connectivity is preserved in both directions. This shows that $v \to b$ cannot be a strong bridge.
This contradiction shows that no vertex can have out-degree at least $2$, so every vertex has out-degree exactly $1$.
Applying the same argument to the reversed graph shows that every vertex has in-degree exactly $1$.
A finite directed graph in which every vertex has in-degree $1$ and out-degree $1$ is a disjoint union of directed cycles. Strong connectivity forces the existence of exactly one cycle containing all vertices, so the entire graph is a single directed cycle.
In a directed cycle, every vertex has exactly two incident edges in the underlying undirected graph, so the underlying degree of every vertex is $2$. This contradicts the assumption that every square has at least three streets leading out of it, which implies underlying degree at least $3$.
Therefore our assumption was false: not every edge is a strong bridge. Hence there exists at least one edge whose removal preserves strong connectivity.
This completes the proof. ∎
Verification of Key Steps
The critical step is the claim that a vertex with two outgoing edges forces a non-bridge. The construction explicitly uses strong connectivity to build an alternate route from one neighbor to another, ensuring that the second outgoing edge is bypassable. The key dependence is that reachability between the two neighbors does not use the edge being tested, so the detour is independent of the deletion.
The second delicate point is the deduction that in-degree and out-degree both equal $1$ implies a disjoint union of directed cycles. This follows because each vertex has exactly one successor and one predecessor, forcing a permutation structure on the vertex set decomposing into cycles.
The final contradiction relies on translating “at least three streets lead out” into underlying undirected degree at least $3$, incompatible with a cycle structure where the degree is exactly $2$.
Alternative Approaches
A different approach uses the theory of strong bridges and dominator trees in directed graphs. One can show that a strongly connected digraph with minimum underlying degree at least $3$ cannot have all edges as dominators, hence must contain a non-critical arc.
Another approach proceeds via ear decompositions of strongly connected digraphs, showing that any such graph with sufficient minimum degree contains an ear whose removal preserves strong connectivity. This perspective is more structural but less elementary than the direct degree-forcing argument above.