Suppose $\Gamma_1(V_1, E_1)$ and $\Gamma_2(V_2, E_2)$ are simple graphs with countably many vertices. And suppose $A_1$ and $A_2$ are initially empty. Suppose two players play the following game: each turn, the first player choses either to add a vertex from $V_1$ to $A_1$ or a vertex from $V_2$ to $A_2$. Then the second player also choses either to add a vertex from $V_1$ to $A_1$ or a vertex from $V_2$ to $A_2$. After it, if the subgraphs induced by $A_1$ and $A_2$ are not isomorphic, the first player wins. Otherwise the game continues. The second player wins, if they are able to keep the game going on indefinitely.

Is it true, that the second player has a winning strategy iff $\Gamma_1 \cong \Gamma_2$?

I know, that if $\Gamma_1 \cong \Gamma_2$ then the second player can prolong the game indefinitely by simply copying the moves of the first player on the different graph. But what’s about the converse? Is it true?


Firstly, can assume that $A_1$ and $A_2$ have the same number of vertices after every pair of moves (otherwise player 2 is giving the game away).

Lemma: If every vertex $v_i\in\Gamma_1$ eventually gets sent to $A_1$ and every vertex $w_i\in\Gamma_2$ gets sent to $A_2$, then there an isomorphism between $\Gamma_1$ and $\Gamma_2$.

After the $i$th pair of moves, a vertex $v_i\in\Gamma_1$ will be sent to $A_1$ and $w_i\in\Gamma_2$ will be sent to $A_2$. The mapping which sends all the $v_i$ to their corresponding $w_i$ is an isomorphism. Any pair of vertices $v_j,v_k\in \Gamma_1$ will both end up in $A_1$ after some number of moves, and they are adjacent iff the corresponding $w_j,w_k$ are adjacent.

Now we can construct a winning strategy for player 1 when the two graphs are not isomorhpic. Player 1 orders all the vertices in both graphs as $v_1,w_1,v_2,w_2,v_3,w_3...$.

At every turn player 1 chooses the next vertex in his ordering which is not already in $A_1$ or $A_2$. Since every vertex in $\Gamma_1$ and $\Gamma_2$ eventually gets chosen, either the play terminates or the two graphs are isomorphic.

| cite | improve this answer | |
  • $\begingroup$ The graphs are infinite. Why must every $v_j, v_k \in \Gamma_1$ end up in $A_1$ after some number of moves? Certainly player $1$ can make it so, but that's not necessary, unless I'm missing some obvious reason why that would be player $1$'s optimal strategy...? $\endgroup$ – antkam Nov 18 '19 at 17:22
  • $\begingroup$ Thanks @antkam for pointing that out. I have edited my answer. $\endgroup$ – Angela Pretorius Nov 18 '19 at 18:29
  • $\begingroup$ +1 for such a nice, direct, simple proof that "exhaustion" is player 1's best strategy. $\endgroup$ – antkam Nov 18 '19 at 18:33

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.