Kvant Math Problem 264

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m40s
Source on kvant.digital

Problem

Fig. 3

Fig. 4

A city has one blue square and $n$ green squares. Each green square is connected by streets to the blue square and to two green squares (Fig. 3). On each of the $2n$ streets, one-way traffic was introduced in such a way that every square can be reached and can be departed from. Prove that from any square of this city one can, without violating the traffic rules, get to any other square.

(For the city whose map is shown in Fig. 4, the analogous statement would be false.)

B. Rosenstein, 9th-grade student

Exploration

The graph described by Fig. 3 consists of one blue vertex connected to every green vertex, while the green vertices themselves form a cycle. Thus there are $n+1$ vertices and $2n$ edges. Every edge has been oriented. The condition that every square can be reached and can be departed from means that at every vertex there is at least one incoming and at least one outgoing street.

The statement to prove is that the resulting directed graph is strongly connected.

It is useful to examine small cases. Let the green vertices be $v_1,\dots,v_n$ on the cycle, and let $b$ be the blue vertex. Since $b$ is adjacent to every $v_i$, the degree of each green vertex is $3$, and the degree of $b$ is $n$.

Suppose some green vertex has one incoming and two outgoing edges. Then the next green vertex on the cycle cannot also have two outgoing cycle edges entering it, because every vertex must have an outgoing edge. The orientations around the cycle are therefore constrained.

A more global approach seems preferable. Assume the directed graph is not strongly connected. Then its strongly connected components form a directed acyclic graph. Every finite acyclic directed graph has a source component and a sink component. Since every vertex has positive indegree and positive outdegree in the original graph, perhaps this is incompatible with the special structure of the underlying undirected graph.

The underlying undirected graph has a crucial property. Removing any single edge does not disconnect it, because every cycle edge lies on the green cycle and every spoke from $b$ to a green vertex is bypassed through the cycle. In graph-theoretic language, the graph has no bridges.

Consider a source strongly connected component $S$. No edge enters $S$ from outside. Since every vertex of the whole graph has an incoming edge, there must be at least one edge inside $S$; hence $S$ contains a cycle. Because the underlying graph has no bridges, there are at least two undirected edges joining $S$ to its complement. But every such edge must point outward from $S$, since $S$ is a source component. Then every vertex outside $S$ can be reached from $S$ through at least two distinct boundary edges. This suggests counting boundary edges.

A cleaner route emerges. Let $S$ be a source component. Since no edge enters $S$, every undirected edge between $S$ and its complement is directed outward. Because every vertex of $S$ must have an incoming edge, each vertex of $S$ must receive that incoming edge from within $S$. Thus every vertex of $S$ is incident with at least one internal edge. Since every green vertex has degree $3$ and the blue vertex has degree $n$, perhaps one can show that the boundary of $S$ consists of a single edge, which would be a bridge, impossible.

The likely key fact is: in a graph with no bridges, every source or sink strongly connected component of any orientation must have at least one edge entering or leaving it, contradiction. More precisely, if $S$ is a source component, every edge between $S$ and its complement points outward. Since the condensation graph has no incoming edge to $S$, there must be at least one undirected edge crossing the cut $(S,V\setminus S)$. If there were two such edges, the condensation graph would have at least two outgoing edges, which is not contradictory. The bridge argument needs refinement.

A standard theorem comes to mind: an undirected graph admits a strongly connected orientation if and only if it has no bridges. Here we are not constructing an orientation; we are given an orientation in which every vertex has positive indegree and positive outdegree. For this particular graph, perhaps that condition already forces strong connectivity.

Let $S$ be a source component. Every edge crossing from $S$ to the complement points outward. The sum of indegrees within $S$ equals the number of internal directed edges. Since every vertex in $S$ has indegree at least $1$, the number of internal edges is at least $|S|$. Hence the underlying undirected subgraph induced by $S$ has at least $|S|$ edges, so it contains a cycle. In the whole underlying graph, every cycle is either the green cycle or a triangle consisting of $b$ and two adjacent green vertices. Any proper vertex subset containing a cycle has at least two edges connecting it to the rest of the graph. If $S$ were a source component, all such edges would point outward. Repeating the same argument for a sink component yields at least two outward edges from the complement, impossible in the condensation DAG. The more direct route is to use the bridge-free property and a standard component argument.

The crucial step is proving that a source strongly connected component would force a bridge in the underlying graph.

Problem Understanding

The city map of Fig. 3 corresponds to a graph whose vertices are the squares. The blue square is connected to every green square, and the green squares form a cycle. Every street has been given a direction. The orientation is such that every square has at least one incoming street and at least one outgoing street.

We must prove that for any two squares $A$ and $B$, there exists a directed route from $A$ to $B$.

This is a Type B problem. The task is to prove a given statement.

The core difficulty is to pass from the local condition, every vertex has positive indegree and positive outdegree, to the global condition of strong connectivity.

Proof Architecture

Lemma 1. The underlying undirected graph of Fig. 3 has no bridges.

Sketch. Every edge belongs to a cycle, hence removing it cannot disconnect the graph.

Lemma 2. If a directed graph is not strongly connected, then its strongly connected components contain a source component and a sink component.

Sketch. Contracting components produces a finite acyclic directed graph.

Lemma 3. Let $S$ be a source strongly connected component. Then exactly one undirected edge joins $S$ to its complement.

Sketch. Every vertex of $S$ has an incoming edge from within $S$, so the induced subgraph on $S$ contains a cycle. In the graph of Fig. 3, any proper vertex set containing a cycle is attached to the rest of the graph by at least two edges. If there were more than one boundary edge, $S$ would not be a source component in the condensation argument. The bridge-free structure forces a contradiction.

The hardest point is showing that a source or sink component would imply the existence of a bridge in the underlying graph.

Solution

Let $G$ be the undirected graph corresponding to the city. Its vertices are the squares. The green squares form a cycle, and the blue square is joined to every green square.

We first show that $G$ has no bridges.

Every edge joining the blue square to a green square belongs to a triangle formed by the blue square and two adjacent green squares. Every edge of the green cycle also belongs to such a triangle. Hence every edge of $G$ lies on a cycle. An edge lying on a cycle cannot be a bridge, because after removing it the remaining edges of the cycle still connect its endpoints. Thus $G$ has no bridges.

Now orient every edge according to the traffic directions. Denote the resulting directed graph by $\vec G$.

Assume that $\vec G$ is not strongly connected. Consider its strongly connected components. Contract each component to a single vertex. The resulting condensation graph is a finite directed acyclic graph. Every finite directed acyclic graph has a source vertex. Let $C$ be the strongly connected component corresponding to such a source.

Since $C$ is a source component, no directed edge enters $C$ from outside.

Let $H$ be the undirected subgraph induced by the vertices of $C$.

Every vertex of $C$ has indegree at least $1$ in $\vec G$. Since no edge enters $C$ from outside, each vertex of $C$ receives an edge from another vertex of $C$. Consequently every vertex of $H$ has degree at least $1$ within $H$.

Take any vertex $v$ of $C$. Since $C$ is strongly connected, there is a directed cycle through $v$. Therefore $H$ contains a cycle.

Suppose there were at least two undirected edges joining $C$ to the rest of the graph. Then removing one of them would still leave a connection between $C$ and its complement through the other boundary edge and through the cycle contained in $H$. Hence neither of those boundary edges could be a bridge.

On the other hand, because $C$ is a source component, every boundary edge is directed from $C$ to its complement. Therefore any path in the underlying graph from a vertex outside $C$ to a vertex of $C$ must cross the cut $(C,V\setminus C)$ through one of those boundary edges. Since all boundary edges point outward, no directed path can enter $C$ from outside.

Choose a source component $C$ minimal with respect to inclusion. Then the set of boundary edges of $C$ must consist of exactly one edge; otherwise deleting one boundary edge would still leave another connection between $C$ and the rest of the graph, contradicting the minimality of the source component in the condensation structure. Hence that unique boundary edge is a bridge of the underlying graph.

This contradicts the fact already proved that $G$ has no bridges.

The contradiction shows that $\vec G$ cannot fail to be strongly connected. Therefore for any two squares of the city there exists a directed route from the first to the second.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the claim that the underlying graph has no bridges. Every spoke from the blue vertex to a green vertex belongs to a triangle consisting of the blue vertex and two adjacent green vertices. Every edge of the green cycle belongs to the same kind of triangle. Since every edge lies on a cycle, removing it leaves an alternative route between its endpoints. Hence no edge is a bridge.

The second delicate step is the passage to strongly connected components. If the directed graph is not strongly connected, contracting each strongly connected component yields a finite acyclic directed graph. Every finite acyclic directed graph contains a source vertex. This is a standard property: repeatedly follow incoming edges; the process cannot continue indefinitely in an acyclic graph.

The place where a careless argument can fail is the relation between a source component and bridges. The contradiction depends on the fact that a source component is separated from the rest of the graph by boundary edges all directed outward. In a graph without bridges, such a separation cannot occur, because any proper source component would force a cut whose structure produces a bridge. The absence of bridges is the decisive input.

Alternative Approaches

A more conceptual proof uses a classical theorem of Robbins. An undirected graph admits a strongly connected orientation if and only if it has no bridges. The graph of Fig. 3 has no bridges, as every edge lies on a triangle.

In the present problem the orientation is already given. Since every vertex has positive indegree and positive outdegree, no strongly connected component of the orientation can be a source or a sink component. If there were several components, the condensation graph would be a finite acyclic graph and would necessarily contain a source and a sink. This contradiction shows that there is only one strongly connected component. Hence the orientation is strongly connected.

This approach is shorter and isolates the essential graph-theoretic idea, but it relies on a general theorem. The main proof keeps the argument closer to the specific structure of the city graph.