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.

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

  • $\begingroup$ I thought the remark showed that this procedure can be applied repeatedly, without compromising the connectedness of the graph obtained by removing the maximum distance nodes selected at each iteration. So, I'm not sure I understand in which sense the result cannot be improved. (Of course, one cannot remove a node from an empty graph, but you covered that.) $\endgroup$ – Fabio Somenzi Feb 11 '17 at 21:52
  • $\begingroup$ @FabioSomenzi Right. It's clear you can iterate this till the graph is empty, or a point. $\endgroup$ – BrianO Feb 11 '17 at 21:56
  • $\begingroup$ @FabioSomenzi The remark was intended to demonstrate that in any connected graph with at least two nodes there are at least two points which can be deleted without disconnecting the graph. That is optimal, as in a straight line graph there are exactly two. I was not speaking about iterating the process on smaller and smaller graphs. $\endgroup$ – lulu Feb 11 '17 at 22:07
  • $\begingroup$ @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$. $\endgroup$ – Fabio Somenzi Feb 12 '17 at 0:16
  • $\begingroup$ @FabioSomenzi Yes. The argument can, I think, be tightened slightly to show that the two guaranteed points can be removed simultaneously. $\endgroup$ – lulu Feb 12 '17 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.