Problem 1336

Solution:

Let $G$ be the graph having the cities as its vertices and the roads as its edges. (This just restates the problem in graph-theoretic language, which we use from now on.) We will look at the components of the graph $G$ and its subgraphs, where a component of a graph is defined to be a maximal connected subset: two vertices are in the same component if and only if it is possible to get from one to the other by following the edges.

The graph $G-S$ has more than one component, since it is disconnected. On the other hand, adding one edge of $S$ to $G-S$ can only connect two of these components; if $G-S$ had more than two components, adding this edge would still leave a disconnected graph and $S$ would not be strategic. So $G-S$ has exactly two components; call them $A, B$. Since these components are not connected to each other in $G-S$, every edge of $G$ connecting $A$ to $B$ must lie in $S$. Conversely, every edge of $S$ must connect $A$ to $B$, since, if it were entirely within $A$ or $B$, it could be added to $G-S$ while leaving the graph disconnected, and $S$ would not be strategic. Thus, $S$ consists exactly of those edges of $G$ which connect $A$ to $B$. Similarly, $G-T$ has two components $C, D$, and $T$ consists precisely of the edges of $G$ which connect $C$ to $D$.

Now, the vertices of $G$ can be represented as a disjoint union of the four sets of vertices $A \cap C, A \cap D, B \cap C$, and $B \cap D$. From our characterizations of $S$ and $T$, we see that $U$ consists of precisely those edges of $G$ which link $A$ to $B$ or $C$ to $D$, but not both. It follows that, when we remove $U$ from $G$, all the remaining edges either link neither pair - and therefore lie entirely within one of our four sets of vertices - or both pairs, in which case they connect $A \cap C$ to $B \cap D$ or $A \cap D$ to $B \cap C$. Thus, $G-U$ contains no edges connecting the set of vertices $(A \cap C) \cup (B \cap D)$ with the vertices $(A \cap D) \cup (B \cap C)$. Furthermore, neither set of vertices is empty: we know that all the edges in $U$ connect these two sets, and $U$ is nonempty because $S \neq T$. So we can choose one vertex from each set, and these two vertices are not connected by any path in $G-U$; thus, $U$ is important.