# Is following function a metric on the set of isomorphism classes of graphs with countably many vertices?

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 sets. 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 game terminates. If the game has terminated on the $$n$$-th turn, then the revenue of the first player is $$\frac{1}{n}$$ and the revenue of the second player is $$n$$. If the game lasts indefinitely, then the revenue of the first player is $$0$$ and the revenue of the second player is infinite.

Let’s define $$d(\Gamma_1, \Gamma_2)$$ as the revenue of the first player, provided that both players use best strategies possible. Is it true, that $$d$$ is a metric on the set of all isomorphism classes of graphs with countable number of vertices?

The proof that $$d(\Gamma_1, \Gamma_2) = 0$$ iff $$\Gamma_1 \cong \Gamma_2$$ can be found here.

However, I do not know, whether the triangle inequality $$d(\Gamma_1, \Gamma_3) \leq d(\Gamma_1, \Gamma_2) + d(\Gamma_1, \Gamma_3)$$ holds here.

• Maybe even $d(\Gamma_1,\Gamma_3)\le\max\{d(\Gamma_1,\Gamma_2),d(\Gamma_2,\Gamma_3)\}$? – bof Nov 18 '19 at 22:27