# Game on a Graph

Assume a game on a Graph $$G$$ with two players called Alice and Bob. They alternate their moves and Alice always begins.

In the beginning Alice puts a coin on arbitrarily vertex of the Graph. In all following moves, the coin must be moved along an edge from $$G$$ to an unvisited vertex of $$G$$ (i.e. a vertex on which the coin has never been placed in the history of the game).

The first player who can no longer make a move (because all neighboring vertices have already been visited) loses the game.

For all matching $$M$$ of the graph $$G$$ there exists a Strategie called $$S_M$$. If the coin is on the vertex $$v$$ before the start of the move, make the following move:

1. If $$v$$ is in a edge $$\{u,v\} \in M$$ and $$u$$ is unvisited, than go along the edge $$\{u,v\}$$ to $$u$$.

2. Otherwise: Give up (the other player wins).

(i) Assume for this $$M$$ isn't a perfect matching and Alice puts in here first move the coin on a vertex which isn't in $$M$$ and than she plays according to $$S_M$$. How can I proof that if Alice lost the game, then $$M$$ is not a maximum matching?

My thought: When I try to prove this with contraposition: $$M$$ is a maximum matching $$\implies$$ Alice wins the game. But i have found a counterexample. Assume a Graph with 3 vertices. Two are connected with one edge, and one vertex is isolated and $$M = \{\}$$, hence $$M$$ is not perfect. Alice puts the coin on the isolated vertex. She wins the game, but $$M$$ is not a maximum matching - how could that be?

Statement 1: If Alice loses then $$M$$ is not a maximum matching.

Statement 2: If Alice wins then $$M$$ is a maximum matching.

These statements do not say the same thing. The task asks you to prove Statement 1. Your counterexample is a counterexample for statement 2.

Maybe this is easier to understand if I add another statement:

Statement 3: If $$M$$ is a maximum matching then Alice wins.

Now statement 3 is equivalent to statement 1. But statement 3 is different from statement 2. In your post you try to prove statement 1 by proving statement 3 (which is also called an indirect proof and this works perfectly fine). But your counterexample is a counterexample for statement 2 and thus does not invalidate statements 1 and 3.

And another idea which might help: Assume that we try to use your 3-vertex graph as counterexample for statement 1. In order to do that we'd have to find a maximum matching on that graph where Alice loses. But that is not possible since a maximum matching on your graph contains the only edge and thus Alice will put the coin on the isolated vertex and win.