G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge…

Concept

Breadth-first search discovers vertices in nondecreasing shortest-path distance from the root. When an undiscovered vertex is first encountered, the edge used for that discovery becomes its tree edge; a later edge to an already discovered vertex does not enter the BFS tree.

Application

1. The root v1 is at level 0.

2. Its adjacent vertices v2, v3, and v4 are all at level 1. They are first discovered while v1 is expanded, so the edges v1v2, v1v3, and v1v4 enter every BFS tree rooted at v1.

3. The edges v2v4 and v3v4 join two vertices already discovered at level 1, so neither can perform a first discovery.

4. Vertex v5 is at level 2 and can first be reached from v2 or v4, depending on the level-1 queue order. Therefore v4v5 is not guaranteed to be selected.

Cross-check

• A BFS parent must lie one level closer to the root. The only level-0 endpoint offered with a level-1 vertex is the edge v1v4.

• Changing the scan order can change the parent of v5, but it cannot change the first-level discovery of v4 from v1.

Hence, the edge v1v4 must be a BFS tree edge.