Problema 4
No país Arnaldos Unidos, existem 
cidades conectadas por 
estradas e, a partir de qualquer cidade, é possível chegar até a capital Arnaldópolis usando as estradas.
Durante os 
primeiros dias do ano, uma das estradas é escolhida em cada dia e tem o seu tráfego interrompido para passar por uma reforma que durará pelo menos dias. Durante qualquer momento desse processo, chamaremos uma cidade de folha se ela não for a capital e estiver conectada a apenas uma outra cidade por uma estrada que não teve seu tráfego interrompido. Para minimizar os transtornos, uma estrada só pode ser reformada uma única vez e, além disso, apenas quando uma das cidades que ela conecta é uma folha. Por exemplo, no mapa a seguir em que a cidade 
é a capital Arnaldópolis, as cidades 
, 
, 
, 
e 
são folhas. Veja que uma reforma iniciada na estrada entre as cidades 
e reduz o número de folhas de 
para 
e que uma reforma no dia seguinte na estrada entre as cidades e mantém o número de folhas constante e igual a .
a) No mapa acima, com 
cidades, determine uma ordem apropriada de reformas para as estradas e, em seguida, determine o número de dias em que a quantidade de folhas não é alterada durante o processo de reformas
b) Supondo agora que 
e que existem inicialmente 
folhas, determine o número de dias em que a quantidade de folhas não é alterada durante um processo qualquer de reformas envolvendo todas as estradas nos primeiros 
dias do ano.
Solução de João Linhares:
a) Ordem: 
Com o número de dias em que o número de folhas não muda é
b) Grafos são um conjunto de vértices e arestas, como na figura abaixo, nessa questão, pode se tomar um grafo tal que cada vértice represente uma cidade e cada aresta represente uma estrada que liga as cidades. Chamamos um grafo de árvore quando ele é conexo, ou seja, existe um caminho que liga todos os vértices( não necessáriamente diretamente) e não existem ciclos, ou seja, independente do vértice, não existe um caminho em que se sai desse vértice e volta para ele mesmo. Deixarei um link no final da solução com materiais de grafos para melhores explicações.
Teorema: Se um grafo 
tem vértices e 
arestas ele é uma árvore (não tem ciclo)
Voltando à solução: Vamos tomar um grafo com vérices(representando as cidades) e arestas(representando as estradas) como ele não tem ciclos, independente do vértice, existe apenas uma aresta que leva para a capital e essa só vai ser reformada uma vez que o vértice seja uma folha.
Ou seja após uma certa quantidade de dias, qualquer vértice que não seja a capital nem uma folha no início das reformas terá apenas arestas ligadas a ele, uma que está ligada a uma folha e outra que leva para o centro e ao cortar a aresta que está ligada à folha, o número de folhas não diminuirá, logo para cada vértice que não é a capital nem folha no início do processo existirá um dia em que o número de folhas não mudam.
Mas existem inicialmente 
vértices desse tipo, logo haveram dias sem o número de folhas mudar.