We looked at a different strategy to test whether there is a path from node s to node t in a directed n-node graph. Here we reformulate that strategy in terms of a two-player game as follows. At any time in the game, White is asserting that a path exists from one particular node to another. Originally she says that there is a path from s to t. On her turn, she names a new node m and asserts that paths exist both from s to m and from m to s. Black then challenges one of these two assertions. White wins the game if her assertion, that a path exists from u to v, becomes one that can be verified because either u = v or there is an edge from u to v. Black wins the game if White has not won after t moves, where t is the least natural such that 2t > n - 1. es

(a) Prove that White has a winning strategy for this game if a path from s to t exists.

(b) Prove that Black has a winning strategy for this game if no path from s to t exists.

P9.10.6 In Excursion 9.7 we looked at a different strategy to test whether there is a path from node s to node t in a directed n-node graph. Here we reformulate that strategy in terms of a two-player game as follows. At any time in the game, White is asserting that a path exists from one particular node to another. Originally she says that there is a path from s to t. On her turn, she names a new node m and asserts that paths exist both from s to m and from m to s. Black then challenges one of these two assertions. White wins the game if her assertion, that a path exists from u to v, becomes one that can be verified because either u = v or there is an edge from u to v. Black wins the game if White has not won after t moves, where t is the least natural such that 2 > n-1. (a) Prove that White has a winning strategy for this game if a path from s to t exists. (b) Prove that Black has a winning strategy for this game if no path from s to t exists. P9.10.6 In Excursion 9.7 we looked at a different strategy to test whether there is a path from node s to node t in a directed n-node graph. Here we reformulate that strategy in terms of a two-player game as follows. At any time in the game, White is asserting that a path exists from one particular node to another. Originally she says that there is a path from s to t. On her turn, she names a new node m and asserts that paths exist both from s to m and from m to s. Black then challenges one of these two assertions. White wins the game if her assertion, that a path exists from u to v, becomes one that can be verified because either u = v or there is an edge from u to v. Black wins the game if White has not won after t moves, where t is the least natural such that 2 > n-1. (a) Prove that White has a winning strategy for this game if a path from s to t exists. (b) Prove that Black has a winning strategy for this game if no path from s to t exists