Computer Science 789 Online Algorithms
Hint 1 for the
Proof of the Game Graph Lemma
To say that Red can win is to say that Red has a winning strategy.
We can define a strategy behaviorly to be a function
S whose domain is the set of all paths which end at red nodes.
If alpha is a path which ends at a red node x,
then S(alpha) = y, for some y for which (x,y) is an edge.

Back to
Course Page
Back to
Assignment Page
Back to
Assignment 1