Prova da Existência de um Caminho Gerador em um Torneio

Vamos supor para fins de contradição que não exista um caminho gerador T no digrafo D que representa a estrutura de um torneio Ou seja para qualquer vértice v existe pelo menos um outro vértice que não pode ser alcançado por nenhum outro caminho Escolhendo um vértice arbitrário v0 e notase que há pelo menos um vértice u que não pode ser alcançado a partir dele dado que não existe um caminho gerador em T No entanto esse vértice inalcançável u precisa dever ter um arco de chegada pois todos os pares de vértices são conectados por uma aresta estrutura de torneio Considerando agora o vértice de chegada do arco que parte de u notase que esse vértice também não puder ser alcançado a partir de v0 devemos continuar repetindo o raciocínio até nenhum vértice ser alcançável a partir de u o que faria com que T fosse desconexo e logo não seguemse a estrutura de um torneio o que nos levaria a uma contradição Portanto a suposição inicial de que não existe um caminho gerador é falsa torneio possui um caminho gerador