Problema 5.1

Foi-me pedido que indicasse aqui qual a solução para o problema 5.1. Recordando. Existe um país no qual todas as estradas são de sentido único. Para além disso existe apenas uma e uma só ligação directa entre todos os pares de cidades. Pretende-se mostrar que existe (pelo menos) uma cidade que pode ser alcançada por estrada a partir de qualquer outra cidade, de modo directo ou de modo indirecto. Neste último caso existe apenas uma cidade de permeio.

Vamos então à solução que nos impõe sermos capazes de alguma abstracção. Vamos escolher uma cidade que tem um número máximo de ligações directas para si. Como é bom de ver ela tem que existir. Na realidade pode mesmo existir mais do que uma. Mas escolhamos uma. Seja C o nome da cidade e m o número de ligações. Vejamos se existe alguma cidade, chamemos-lhe X, que não esteja ligada directamente a essa cidade. Se não existir então a prova está terminada. E se existir? Se existir ela tem que estar ligada a uma das cidades que se ligam à nossa cidade escolhida. E porquê? Bem porque se não X teria para si m+1 ligações directas: todas as que se ligam a C mais a ligação de C para X. Não se esqueça que tem que existir uma ligação entre todas as cidades! E isso não pode ser, pois por hipótese m é o número máximo de ligações directas! Com X é uma cidade qualquer não ligada directamente a C isto completa a nossa prova, pois fica ligada indirectamente a C e só com uma cidade pelo meio!

Q.E.D.