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.
 A: 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.
