Dois amigos desenham um grafo G, colocam um marcador sobre um vértice e vão jogar um jogo. Um deles toma o papel de Explorador e a cada turno escolhe uma distância, o outro – no papel de Diretor – move então o marcador para um vertíce a essa distância. Aqui o objetivo do Explorador é maximizar o número de vértices visitados e o do Diretor é minimizar este número.

Qual é o número de vértices visitado se ambos os jogadores fizerem as melhores jogadas possíveis?

Originalmente este jogo foi definido – e resolvido – apenas para grafos cíclicos como uma reformulação de um problema em ciência da computação. O que é que conseguimos descobrir para outras classes de grafos?