A PROVA DE UMA IA, REDESENHADA PARA HUMANOS
Desenhe alguns pontos e ligue alguns deles com linhas. Os matemáticos chamam isso de grafo; os pontos são vértices, as linhas são arestas, e o número de linhas que tocam um ponto é o seu grau. Uma árvore é um grafo sem ciclos que se mantém inteiro numa só peça, como um galho ramificado; uma árvore com t pontos tem sempre t − 1 linhas.
No início dos anos 1960, Paul Erdős e Vera T. Sós fizeram uma pergunta simples: quantas linhas obrigam um grafo a conter todas as árvores de um dado tamanho? A resposta deles, a conjectura de Erdős–Sós, é a seguinte:
Se um grafo tem grau médio maior que t − 2, ele contém todas as árvores com t vértices.
O limiar é exato. Pegue cópias separadas de um grafo completo com t − 1 pontos, em que cada par está ligado: cada ponto tem exatamente t − 2 vizinhos, mas nenhuma peça é grande o bastante para conter uma árvore de t pontos. A dificuldade está na palavra média. Se cada ponto tivesse pelo menos t − 1 vizinhos, seria possível encaixar uma árvore ramo por ramo sem problema. Mas uma média não diz nada sobre nenhum ponto individual: alguns podem ter centenas de vizinhos, outros quase nenhum.
Sessenta anos de respostas parciais
Segundo o histórico relatado no artigo, o problema data de 1962–1964 e tornou-se central no ramo da matemática que estuda quantas arestas obrigam o aparecimento de um dado padrão. Casos particulares foram caindo: estrelas, caminhos, estrelas duplas, árvores com poucos ramos. No início dos anos 1990, quatro matemáticos — Ajtai, Komlós, Simonovits e Szemerédi — anunciaram uma prova para árvores muito grandes, mas artigos recentes observam que nenhum manuscrito completo foi jamais publicado. Outros resultados parciais chegaram em 2021, 2024 e 2026. Em 4 de setembro de 2026, Reed e Stein publicaram uma prova para grafos grandes e densos, que afirmam ter sido desenvolvida sem IA.
Depois veio um relatório. Em setembro de 2026, Tom Adamczewski e Thomas Bloom, num documento chamado FrontierMath Erdős, atribuíram uma prova da conjectura completa a uma versão pré-lançamento de um modelo de IA, o GPT-6 Astra. O argumento de contagem original é público, e um repositório que o acompanha registra a busca autônoma da IA pela prova e uma verificação formal na linguagem de verificação de provas Lean. Os autores do relatório também convocaram especialistas humanos a escrever relatos mais completos e tradicionais.
Revelar um grafo um ponto de cada vez
Jay Cummings, da California State University, Sacramento, responde a esse apelo. Seu artigo de 27 páginas mantém o argumento de contagem central da IA, mas muda a forma de contá-lo:
- Revelar o grafo aos poucos. Liste os vértices em alguma ordem e descubra-os um a um, junto com as arestas entre os que já foram mostrados.
- Pedir mais. Em vez de qualquer cópia da árvore, procure uma cuja “raiz” escolhida fique exatamente no primeiro vértice. Pedir mais torna a prova mais fácil.
- Contar os vizinhos precoces. São os vizinhos do primeiro vértice que aparecem antes de surgir uma tal cópia. Some-os sobre todas as ordens possíveis.
- Limitar o total. Trocando vértices ou blocos inteiros da ordem — movimentos que sempre podem ser desfeitos —, Cummings mostra que, em média sobre todas as ordens, há no máximo t − 2 vizinhos precoces.
O passo final é curto. Se o grafo não contivesse nenhuma cópia da árvore, todo vizinho do primeiro vértice seria precoce, em todas as ordens. Em média sobre todas as ordens, isso é exatamente o grau médio — que, por hipótese, ultrapassa t − 2. Contradição: a árvore tem de estar lá.
A prova usa apenas o total dos graus, não a forma como estão distribuídos. Cummings dá também uma versão probabilística e trabalha exemplos com árvores de quatro e cinco vértices em grafos concretos.
Uma prova em livro ilustrado
O artigo contém 32 figuras. Termina com uma consequência clássica: pinte todas as linhas de um grafo completo com q cores, e uma das cores conterá sempre uma dada árvore assim que o grafo tiver q(t − 2) + 2 vértices. Numa declaração final, Cummings explica que desenvolveu o texto num longo diálogo com o ChatGPT, que as novas ideias de apresentação — os vizinhos precoces, as partições explícitas, os desenhos — são dele, e que verificou tudo e assume total responsabilidade.
Ele compara o seu relato com outros recentes, de Riordan e Scott, de Wood e de Frederickson, e observa que o método já foi estendido a redes com direções e a “hipergrafos”, sendo algumas dessas extensões também atribuídas ao GPT-6 Astra. A contribuição dele, escreve, é “uma exposição visual do argumento centrada no leitor, não uma nova resolução da conjectura”.
