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