O Jogo

O jogo se inicia com dois jogadores $A$ e $B$ e um grafo $G$. O jogador $A$ começa o jogo escolhendo um vértice $v_0$, então $B$ escolhe um vértice $v_1$ e assim por diante, sabendo que $v_i$ é adjacente $v_{i+1}$ e se $i\neq j$, então $v_i \neq v_j$, perde quem ficar sem jogadas possíveis.

Possibilidades de jogadas: Para sabermos quem ganhou o jogo basta sabermos se $G$ possui ou não emparelhamento perfeito.

Se $G$ possui um emparelhamento perfeito, $B$ tem estratégia vencedora, isto é, o jogador $A$ começa jogando,e ,como o emparelhamento é perfeito, $B$ pode escolher uma aretsa do emparelhamento saindo do vértice jogado por $A$. Se $A$ conseguir jogar de novo, vai ser por uma aresta que está fora do emparelhamento (pois elas são independentes). Mas o outro vértice que $A$ jogou tem que estar emparelhado também, $B$, então, só precisa seguir a aresta do emparelhamento e ganhará o jogo.

Caso contrário, se $G$ não possui emparelhamento perfeito, $A$ tem estratégia vencedora.

• Suponha $M$ emparelhamento máximo, jogue como $A$ um $v_0$ emparelhado.
• Se $B$ jogar algo emparelhado, basta $A$ jogar um vértice emparelhado, em dado momento $B$ não conseguirá escolher um ponto emparelhado, pois $G$ não possui emparelhamento perfeito.
• Se $B$ jogar algo não emparelhado, teríamos um caminho alternante, primeiro dentro do emparelhamento, depois fora, terminando fora, podemos então inverter quem está dentro com quem está fora do emparelhamento, dessa forma teremos um emparelhamento com um elemento a mais.