Tenuous Path Connectivity

I'm now taking an algorithms class for my masters program. I had to do a kind of neat homework problem this week, for which I think I actually managed to do a proper proof for. Assuming I did the problem right, this is kind of a big deal for me, because I've alwys been pretty awful at proofs. I thought I'd write up my solution, just for fun.

The Problem

You have an undirected graph that represents paths between various places. Intuitively, there is a concept that two nodes far away from each other have a more tenuous connection - that is, they are susceptible from being isolated from each other.

Given a graph of n nodes, and two nodes, s and t that have a distance greater than n/2, show that there is always some node v (different from s and t) that, if deleted, severs all paths between s and t.

My solution

We received a hint to use a breadth-first-search to try to solve this. A BFS basically starts at some node and makes multiple steps, at each point finding all of the nodes one step farther away from the starting point. Visually, it might look like rippling outwards from some point.

More usefully, when you run a BFS on a graph, one representation that is helpful to work with is that it turns the graph into several "layers", L0 through Ln. L0 is the starting node itself, L1 is all of the immediate neighbors of the starting node, and more generally, Ln is all the nodes n hops away from the start.

A direct application of a BFS doesn't seem likely to find any particular special node to delete. We're also given that the node always exists, so there must be some criterion for determining it. My first guesses were all along the lines of finding a node that minimizes or maximizes some aspect of the connectivity. For example, finding a node in a layer that has the most connections to the next layer. If such a node were deleted, perhaps it would knock out too many connections to support a second path to the finish.

None of these attempts worked. Finally, after drawing a bunch of graphs, I noticed an interesting property: they all had one layer in the BFS that had just one node - a single point of failure. I did several example graphs and wasn't able to construct one with both all layers including more than one node and the start and finish being at minimum distance n/2.

If this property were really true, then all we'd have to do is perform a BFS from the start and look for the first layer in which there is only one node.

Proof - by contradiction

n = number of nodes in the graph
d = distance from s to t = number of layers in the BFS from s to t = (n / 2) + 1

For the contradiction, assume there is such a graph that has two independent paths from s to t, so that if any node in one path is severed, the other still remains. In this graph, every layer L1 through Ld-1 (s is in L0, and t is in Ld) contains 2 nodes.

The total number of nodes in this graph is now:

1 +                            (L0)
2 * (d - 1) +                  (L1 through Ld-1)
1                              (Ld)
= 2 + 2d - 2
= 2d
= 2 ((n / 2) + 1)              (d must be (n / 2) + 1)
= n + 2

Contradiction: in the beginning we stated that there are n nodes in the graph, but in this minimal graph that includes two independent paths, there must be n+2 nodes. So this proves that you can't satisfy the minimum distance constraint, the number of nodes in the graph, and have two or more nodes in each level of the BFS. One constraint will always yield.

I hope this is the right answer, because I feel pretty cool for having come up with it.

Update, 11/5: I got a 10/10 on this problem. Woot.