Random’s Solution path
•Claim: always have a path from startNode to currNode
–à currNode=exitNode, we have a solution
•Proof by Induction
–Restatement: after i moves
–Base case:
•0 moves (currNode=startNode)
–Induction step:
•have path for i moves
•prove for i+1 moves.