UM QUEBRA-CABEÇA DE GRAFOS DOS ANOS 1960 FINALMENTE SE FECHA

Pegue alguns pontos e ligue alguns pares deles com linhas: os matemáticos chamam isso de grafo, os pontos de vértices e as linhas de arestas. Um ciclo é um laço fechado que passa por vértices distintos e volta ao ponto de partida. Uma pergunta natural é se as arestas de um grafo podem ser divididas — cada aresta usada exatamente uma vez — em ciclos.

A resposta é conhecida há muito tempo, como lembra o artigo: isso é possível exatamente quando cada vértice toca um número par de arestas. Esses grafos são chamados de eulerianos. A pergunta seguinte é quantos ciclos são necessários. E, para grafos em que só ciclos não bastam, também se permitem arestas avulsas como peças.

A conjectura

Nos anos 1960, Erdős e Gallai conjecturaram que as arestas de todo grafo com n vértices podem ser divididas em um número de ciclos e arestas avulsas no máximo proporcional a n — escrito O(n). Erdős a incluiu em várias de suas coleções de problemas em aberto. Uma conjectura relacionada, de Hajós, pede no máximo (n − 1)/2 ciclos em todo grafo euleriano.

Linear é o melhor que se poderia esperar: Erdős mostrou que alguns grafos precisam de cerca de 1,5 n peças. A questão era se alguma constante vezes n sempre basta.

Cinquenta anos de limites que avançam devagar

Os próprios Erdős e Gallai notaram um método simples: retirar repetidamente o ciclo mais longo. Ele dá cerca de n log n peças — e, segundo o artigo, esse continuou sendo o melhor limite geral por quase cinquenta anos. Mais recentemente, Conlon, Fox e Sudakov o reduziram para n log log n, e depois Bucić e Montgomery para n log* n, em que log* n — o número de vezes que é preciso tirar um logaritmo para ficar abaixo de um — cresce de forma inimaginavelmente lenta. Essas abordagens funcionavam em rodadas, e cada rodada custava cerca de n ciclos, então o número de rodadas sempre acabava entrando na contagem final. A conjectura também já tinha sido provada para famílias especiais, como os grafos aleatórios.

Pesos que pagam pelos laços

Jaehoon Kim, do KAIST, na Coreia do Sul, agora prova a conjectura: existe uma constante fixa C tal que todo grafo com n vértices se divide em no máximo Cn ciclos e arestas. Como corolário, a conjectura de Hajós vale a menos de um fator constante.

A prova abandona as rodadas. Um único procedimento retira ciclos e arestas um de cada vez, e o total é controlado por duas quantidades que ficam, cada uma, abaixo de uma constante vezes n.

• Um potencial baseado nos graus. Cada vértice recebe um peso que diminui com seu número de arestas, aproximadamente 1 / (grau × log² grau). Um ciclo é pesado se os pesos de seus vértices somam pelo menos 1. Retirar um ciclo pesado reduz um “potencial” global em pelo menos 1, e esse potencial começa em no máximo uma constante vezes n. Assim, ciclos pesados só podem ser retirados O(n) vezes.
• O número de vértices. Quando não resta nenhum ciclo pesado, o grafo é “leve” — e o principal teorema novo mostra que um grafo leve com graus grandes deve conter uma região densa, quase fechada. Essa região é dividida em um número de ciclos e arestas proporcional ao seu tamanho, depois do qual pelo menos um cinquenta avos de seus vértices fica com no máximo duas arestas e sai de cena de vez. Como cada vértice só pode sair uma vez, essa parte também custa O(n).

Dentro das partes densas do grafo, trechos de caminhos são fechados em um único ciclo por caminhos de ligação que passam por “expansores”; uma coloração aleatória mantém separados os caminhos de ligação de um mesmo ciclo. — Figura 3, Kim (2026), arXiv:2610.07840.

Para dividir essas regiões densas, a prova amplia o conjunto de ferramentas de Bucić e Montgomery com “expansores” robustos — grafos em que todo conjunto de vértices tem muitos vizinhos — e colore os vértices ao acaso para que os caminhos de ligação de um mesmo ciclo nunca colidam.

O que ainda está em aberto

A constante C é enorme, e o autor não tentou otimizá-la. Encontrar a melhor constante — de pelo menos 1,5 — continua em aberto, assim como a conjectura exata de Hajós e uma conjectura relacionada de Gallai sobre a divisão de grafos em caminhos. O truque dos pesos só precisa de pesos cuja soma convirja, e o autor sugere que ele poderia servir em outros problemas de decomposição.

Este é um preprint de um único autor, ainda não verificado por revisão por pares.

Conflito de interesses. O autor declara ter usado amplamente o ChatGPT (OpenAI) e o Claude (Anthropic) para desenvolver os argumentos e preparar o texto e as figuras, e afirma ter verificado todos os resultados e assumir total responsabilidade pelo artigo. O texto que você está lendo também foi escrito pelo Claude.