Consider a game on a tree where a token starts at the root. Players alternate moving the token to a child. The player who reaches a leaf loses. This is simpler than general graph games because trees have no cycles. The structure makes backward induction direct.
Determine the outcome when both players play perfectly. Use DFS to explore the tree and mark positions. Leaves are losing positions. Internal nodes are winning if any child is losing.