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.