Exercise 2: Tracing DFS From Vertex 1, Compared to BFS — Possible Solution
====================================================================

GIVEN
------------------------------
1 connects to 2, 3 (visit 2 before 3)
2 connects to 4
3 connects to 5, 6 (visit 5 before 6)

STEP-BY-STEP DFS TRACE
------------------------------
Visit 1. order = [1]
  First unvisited neighbor of 1: 2. Dive in.

Visit 2. order = [1,2]
  First unvisited neighbor of 2: 4. Dive in.

Visit 4. order = [1,2,4]
  4's only neighbor (2) is already visited - backtrack to 2.
  2 has no more unvisited neighbors - backtrack to 1.

  Next unvisited neighbor of 1: 3. Dive in.

Visit 3. order = [1,2,4,3]
  First unvisited neighbor of 3: 5. Dive in.

Visit 5. order = [1,2,4,3,5]
  5's only neighbor (3) is already visited - backtrack to 3.

  Next unvisited neighbor of 3: 6. Dive in.

Visit 6. order = [1,2,4,3,5,6]
  6's only neighbor (3) is already visited - backtrack to 3, then 1.
  No more unvisited vertices - traversal complete.

FINAL DFS ORDER
------------------------------
1, 2, 4, 3, 5, 6

COMPARING TO EXERCISE 1's BFS ORDER
------------------------------
BFS order: 1, 2, 3, 4, 5, 6
DFS order: 1, 2, 4, 3, 5, 6

The two orders diverge starting at the third position: BFS visits 3
(vertex 1's second neighbor) before touching vertex 4, since BFS
finishes all of level 1 before moving to level 2. DFS instead fully
commits to exploring vertex 2's entire branch (reaching 4) before ever
backtracking to try vertex 1's other neighbor, 3 - exactly this
chapter's own "dive fully before backtracking" behavior.

WHY THIS WORKS AS AN ANSWER
------------------------------
The trace follows this chapter's own stack/recursion-based DFS method,
explicitly showing each dive-and-backtrack step, and the final order
is compared directly against Exercise 1's BFS result to pinpoint
exactly where and why the two traversals diverge.