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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.