Duas pessoas jogam o seguinte jogo sob um grafo G: Jogador 1 começa pela escolha de qualquer vértice. Cada escolha subsequente deve ser adjacente...

Se G tem um emparelhamento perfeito, então o segundo jogador tem uma estratégia vencedora. Para provar isso, vamos supor que o primeiro jogador comece escolhendo um vértice v1. Como G tem um emparelhamento perfeito, cada vértice em G está emparelhado com outro vértice. Portanto, o segundo jogador pode escolher o vértice adjacente a v1 que está emparelhado com outro vértice. O primeiro jogador, em seguida, deve escolher o vértice adjacente ao vértice escolhido pelo segundo jogador, que também está emparelhado com outro vértice. Esse processo continua até que um jogador não possa mais fazer uma jogada válida. Como G tem um emparelhamento perfeito, cada vértice em G está emparelhado com outro vértice, então sempre haverá um vértice adjacente disponível para o segundo jogador escolher. Portanto, o segundo jogador sempre terá uma jogada válida e, eventualmente, será o último a jogar, ganhando o jogo. Se G não tem um emparelhamento perfeito, então o primeiro jogador tem uma estratégia vencedora. Para provar isso, vamos supor que G não tem um emparelhamento perfeito e que o primeiro jogador comece escolhendo um vértice v1 que não está emparelhado com nenhum outro vértice. O segundo jogador deve, então, escolher um vértice adjacente a v1 que também não está emparelhado com nenhum outro vértice. O primeiro jogador, em seguida, deve escolher um vértice adjacente ao vértice escolhido pelo segundo jogador que também não está emparelhado com nenhum outro vértice. Esse processo continua até que um jogador não possa mais fazer uma jogada válida. Como G não tem um emparelhamento perfeito, pode haver vértices que não estão emparelhados com nenhum outro vértice. Portanto, o primeiro jogador sempre terá uma jogada válida e, eventualmente, será o último a jogar, ganhando o jogo. A dica para a segunda parte é importante porque, se o primeiro jogador começar com um vértice que está emparelhado com outro vértice, o segundo jogador pode simplesmente escolher o vértice emparelhado e continuar a jogar de forma a garantir que ele seja o último a jogar e, portanto, ganhe o jogo.