Skip to main content

Distance boundaries from BFS tree on undirected graphs


As we have talked on the seminar, if we construct from some vertex uu BFS tree on an undirected graph, we can obtain:

  • lower bound of length of the shortest path between 2 vertices from the height difference
  • upper bound of length of the shortest path between 2 vertices from the path through the root

Lower bound

Consider the following graph:

We run BFS from the vertex aa and obtain the following BFS tree:

Let's consider pair of vertices ee and hh. For them we can safely lay, from the BFS tree, following properties:

  • lower bound: 22
  • upper bound: 44

By having a look at the graph we started from, we can see that we have a path ‹e,j,he, j, h› that has a length 2. Apart from that we can also notice there is another path from ee to hh and that is ‹e,a,c,i,d,he, a, c, i, d, h›. And that path has a length of 55. Doesn't this break our statements at the beginning? (I'm leaving that as an exercise ;))

Proof by contradiction

Let's keep the same graph, but break the lower bound, i.e. I have gotten a lower bound 22, but “there must be a shorter path”! ;)

Now the more important question, is there a shorter path in that graph? The answer is no, there's no shorter path than the one with length 22. So what can we do about it? We'll add an edge to have a shorter path. Now we have gotten a lower bound of 22, which means the only shorter path we can construct has 11 edge and that is ‹e,he, h› (no intermediary vertices). Let's do this!

Okay, so we have a graph that breaks the rule we have laid. However, we need to run BFS to obtain the new BFS tree, since we have changed the graph.


Do we need to run BFS after every change?

­I am leaving that as an exercise ;)

Oops, we have gotten a new BFS tree, that has a height difference of 1.


Try to think about a way this can be generalized for shortening of minimal length 3 to minimal length 2 ;)