Alexa and Brad play the following game on the graph shown be

Alexa and Brad play the following game on the graph shown below. Alexa goes first and colors a vertex green and then Brad colors a vertex red. The couple alternate turns in this manner. No adjacent vertex can be colored the same color. The game continues until one player has no moves left and then that player loses. If Alexa states, \"I\'m always gonna color vertex VI first\" and Brad replies, \"Well then, I\'m gonna color vertex V6 second\", write the sample space of all possible vertex sequences in the form V1-V6-V7-V?-.... and clearly state who wins each sequence. Use your sample space to determine the probability that Alexa wins using this strategy.

Solution

Vertex 1 -> Green

Vertex 6-> Red

Now alexa ca\'t color vertex 2 and 4 as Red, so he can choose 3 and 5

if he chooses 3

V1-V6-V3-V2 (now Alexa can\'t color 4 because it is connected to 1 and 5 is already connected to 3) - Brad Wins

V1-V6-V3-V2 (Brad wins, alexa can\'t color)

V1-V6-V3-V4

Now suppose alexa chooses 5

V1-V6-V5

Now Brad chooses either 2 or either 4

Let us say he has choosen 4

V1-V6-V5-V4(Brad wins) since alexa still can\'t color any vertex

V1-V6-V5-V2 (Brad wins)

Hence there are four possible cases

V1-V6-V5-V4

V1-V6-V5-V2

V1-V6-V3-V2

V1-V6-V3-V4

In all the four games, alexa will lose the game