# Subway & Graphs

In the city there is a subway. You can get from any station to any other one. How can I prove that if we close one of the stations ( it can be picked),you won't be able to drive through it), we will be able to get from any station to any other one.

• It isn't generally true. If the stations were, say, arranged in a line, then removing one in the middle disconnects the graph. – lulu Feb 9 '17 at 17:12
• We can choose the bottom one. – idliketodothis Feb 9 '17 at 17:15
• Oh, you get to pick which one to close? That's very different. I suggest editing the post to make that clear. – lulu Feb 9 '17 at 17:17

We want to show that there is some stop that can be removed without disconnecting the graph. to do it, choose a stop, $s_0$ at random. Then, for a stop $s$, define $d(s)$ to be the length of the shortest path (in terms of the number of stops) from $s_0$ to $s$. Now let $s^*$ be a stop such that $d(s^*)$ is maximal. We claim that you can always remove $s^*$ without disconnecting the graph.
To see this, note that, for $s\neq s^*$ the shortest path from $s_0$ to $s$ can not go through $s^*$ or it would have length greater than the max. Thus, after deleting $s^*$, there is still a path from $s_0$ to $s$. As any stop can reach $s_0$, any stop can reach any other and we are done.
Remark: this shows that there are at least two stops which can be deleted without disconnecting the graph (well, assuming there are at least two stops on the map, anyway). To see that, run through the method once to yield $s^*$, now do it again starting with $s^*$. Considering the case where the stops are arranged in a line we see that this result can not, in general, be improved.
• @lulu Thanks for the detailed response. Here's how I see it. The theorem can equivalently be stated as follows: Every connected graph with $n$ nodes contains connected subgraphs with $m$ nodes for all $m$ such that $0 < m \leq n$. In the case of five nodes in a straight line from left to right, I can remove the two leftmost and the two rightmost nodes and be left with a connected graph. The proof relies on nodes at maximum distance from $s_0$, of which there may be just one. For the line graph no more than two, but for some other graphs, up to $n-1$. – Fabio Somenzi Feb 12 '17 at 0:16