Quando as linhas centrais das ruas de uma cidade podem ser pintadas sem percorrer uma rua mais de uma vez? (Suponha que todas as ruas sejam de mão dupla.)
Passo 1
O enunciado pede para pintar a linha central de cada rua de uma cidade sem percorrer nenhuma rua mais de uma vez. Isso equivale a encontrar, num grafo onde vértices são cruzamentos e arestas são ruas de mão dupla, um percurso que use cada aresta exatamente uma vez. O conteúdo envolvido é Teoria dos Grafos, mais precisamente trilhas e circuitos eulerianos.
Passo 2
Para modelar o problema, associamos cada cruzamento a um vértice e cada rua de mão dupla a uma aresta não-direcionada. Assim, pintar todas as ruas sem repeti-las significa passar por cada aresta exatamente uma vez, isto é, encontrar uma trilha que percorra todas as arestas do grafo.
Passo 3
Um grafo é conexo se, para quaisquer dois vértices, existe um caminho que os une. Se o grafo não for conexo, não há como pintar todas as ruas numa única caminhada, pois faltarão componentes isolados.
Passo 4
O Teorema de Euler afirma que, num grafo conexo, existe trilha que percorre cada aresta exatamente uma vez (trilha euleriana) se e somente se o número de vértices de grau ímpar for igual a 0 ou a 2.
Passo 5
Portanto, para pintar as ruas sem repetir nenhuma delas é necessário e suficiente que o grafo das ruas seja conexo e tenha exatamente 0 ou 2 vértices de grau ímpar. No caso de 0 vértices ímpares, podemos começar e terminar no mesmo cruzamento; no caso de 2, começamos num cruzamento de grau ímpar e terminamos no outro.
Resposta
As linhas centrais podem ser pintadas sem repetir ruas se, e somente se, o grafo associado às ruas for conexo e tiver exatamente 0 ou 2 vértices de grau ímpar.