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...

O jogo descrito é conhecido como "Jogo do Caminho Alternado". A prova para os dois itens é a seguinte: 1. Se G tem um emparelhamento perfeito, então o segundo jogador tem uma estratégia vencedora. Para provar isso, suponha que o primeiro jogador comece em um vértice v. Como G tem um emparelhamento perfeito, cada vértice tem uma aresta incidente que não é usada por nenhuma outra aresta do emparelhamento. Assim, o segundo jogador pode sempre escolher um vértice adjacente a v que não tenha sido visitado antes. Como G tem um emparelhamento perfeito, sempre haverá um vértice adjacente não visitado. Como o emparelhamento é perfeito, o segundo jogador sempre terá uma jogada disponível e, portanto, vencerá o jogo. 2. Se G não tem um emparelhamento perfeito, então o primeiro jogador tem uma estratégia vencedora. Para provar isso, suponha que o segundo jogador tenha uma estratégia vencedora. Então, o segundo jogador pode sempre escolher um vértice adjacente ao vértice escolhido pelo primeiro jogador que não tenha sido visitado antes. Como o segundo jogador tem uma estratégia vencedora, ele sempre terá uma jogada disponível. No entanto, isso significa que G tem um emparelhamento perfeito, o que é uma contradição. Portanto, o segundo jogador não pode ter uma estratégia vencedora e, portanto, o primeiro jogador tem uma estratégia vencedora.