Exercise 3: Why BFS Guarantees Shortest Paths and DFS Doesn't — Possible Solution
====================================================================

WHY BFS GUARANTEES THE SHORTEST PATH
------------------------------
Per this chapter's own level-by-level mechanism, BFS processes every
vertex at distance 1 from the start completely before touching any
vertex at distance 2, every vertex at distance 2 completely before
distance 3, and so on. This means that by the time BFS ever reaches
a given vertex for the first time, every possible SHORTER path to
that vertex (using fewer edges) must have already been fully explored
in an earlier level - there is no way for BFS to "skip ahead" and
discover a vertex late via a short path, because all short paths from
earlier levels are guaranteed to have already been checked. The very
first time BFS visits any vertex is therefore automatically via the
fewest possible edges.

WHY DFS HAS NO SUCH GUARANTEE
------------------------------
Per this chapter's own dive-then-backtrack mechanism, DFS commits
immediately and fully to one single path, potentially very long,
before ever backtracking to check whether a much shorter path to the
same destination might exist through a completely different branch.
If DFS happens to dive down a long winding route and reaches a vertex
that way, it has no built-in mechanism to notice or prefer a shorter
path that might have been available by exploring a different neighbor
first - it simply reports however it happened to get there via its
own depth-first order, not the shortest way.

A CONCRETE ILLUSTRATION FROM THIS CHAPTER'S OWN EXERCISES
------------------------------
In this chapter's own Exercise 1/2 graph, DFS reaches vertex 4 as its
third visited vertex (1, 2, 4), diving fully down the 1-2-4 branch
before ever considering vertex 3. If a different neighbor ordering or
a differently shaped graph existed where a shorter route to some
vertex existed through an unexplored branch, DFS would have no way of
"knowing" to prefer it - it only follows its own already-chosen path
until forced to backtrack.

WHY THIS WORKS AS AN ANSWER
------------------------------
The explanation is grounded directly in this chapter's own stated
mechanisms for each traversal - BFS's level-by-level processing and
DFS's commit-then-backtrack behavior - explaining specifically WHY the
first arrival at a vertex differs in each case, rather than simply
restating that "BFS finds shortest paths" as an unexplained fact.