Phase 1: Naive DFS gets stuck — feel the failure

The Wall: Greedy DFS Gets Trapped

Five flight tickets. Every ticket must be used exactly once. Starting at JFK, the obvious approach: greedily pick the lexicographically smallest next airport at each step. Step through the trace and see where it breaks.

FIG. 1 — TICKETS — SORTED ADJACENCY
JFK[ATL, SFO]
ATL[JFK, SFO]
SFO[ATL]