UM LIMITE PARA AS REDES, AGORA PROVADO PARA QUALQUER TAMANHO
Pegue alguns pontos e ligue alguns pares deles por linhas. Os matemáticos chamam isso de grafo: os pontos são seus vértices, as linhas, suas arestas, e a distância entre dois vértices é o menor número de arestas necessário para ir de um ao outro. Agora acrescente duas regras. Todo par de vértices deve estar a uma distância de no máximo 2 — ligados diretamente ou por meio de um vizinho comum. E nenhuma aresta pode sobrar: apague qualquer uma delas, e algum par fica a mais de dois passos de distância. Um grafo assim é chamado de diâmetro-2-crítico. Quantas arestas ele pode ter?
O teto de Mantel e um palpite mais ousado
Em 1907, Mantel provou que um grafo de n vértices sem triângulo — sem três vértices todos ligados entre si — tem no máximo ⌊n²/4⌋ arestas: n ao quadrado dividido por quatro, arredondado para baixo até um número inteiro. Só um grafo atinge esse teto, o grafo bipartido completo equilibrado: dois grupos de tamanhos tão iguais quanto possível, cada vértice de um ligado a cada vértice do outro, nenhuma aresta dentro de um grupo.
Todo grafo sem triângulo que não pode receber mais uma aresta sem criar um triângulo é diâmetro-2-crítico. O inverso não vale: alguns grafos diâmetro-2-críticos contêm triângulos.
Um grafo diâmetro-2-crítico com 7 vértices e 9 arestas, que contém o triângulo v1v3v5. Apagar v1v3 destrói o único caminho de dois passos entre v2 e v3; apagar uma aresta fora do triângulo deixa suas extremidades sem caminho de dois passos. — Figura 1, Das & Fox (2026), arXiv:2610.39032.
O palpite era que os triângulos não trazem nenhuma vantagem: um grafo diâmetro-2-crítico de n vértices continua tendo no máximo ⌊n²/4⌋ arestas, e o grafo bipartido completo equilibrado continua sendo o único a atingir esse valor. O teorema de Mantel decorreria como caso particular. Para os 7 vértices da figura, o teto é de 12 arestas.
Uma torre de 2
Segundo Erdős, conforme relatado por Zoltán Füredi, a questão remonta a trabalhos de Ore na década de 1960. Ján Plesník enunciou o limite de arestas como conjectura em 1975; Murty e Simon a propuseram de forma independente e acrescentaram que o grafo bipartido completo equilibrado é o único caso extremo — daí a conjectura de Murty–Simon. Nas décadas de 1970 e 1980, limites da forma c·n² foram baixando, com c cada vez mais perto de 1/4.
Em 1992, Füredi provou a conjectura para todo n suficientemente grande, com métodos de regularidade — ferramentas derivadas do lema da regularidade de Szemerédi. O preço era o tamanho de partida: n tinha de ser pelo menos uma torre de 2 com altura de aproximadamente 10¹⁴, isto é, 2 elevado a 2 elevado a 2…, calculado de cima para baixo — cada 2 elevado à potência de tudo o que está acima dele —, com cerca de 10¹⁴ algarismos 2 empilhados. Abaixo desse tamanho, só famílias particulares de grafos tinham sido resolvidas.
Arestas contra arestas ausentes
A nova prova, de Sanjana Das e Jacob Fox, do Departamento de Matemática da Universidade Stanford, vale para todo n a partir de 3. Ela usa um emparelhamento maximal: um conjunto de arestas, sem duas que compartilhem um vértice, ao qual não se pode acrescentar mais nenhuma aresta sem que duas delas se encontrem. Um emparelhamento em n vértices contém no máximo ⌊n/2⌋ arestas.
O lema-chave: num grafo diâmetro-2-crítico, para qualquer emparelhamento maximal, as arestas fora do emparelhamento nunca são mais numerosas do que as não arestas — os pares de vértices que não estão ligados. O resto é aritmética. O dobro do número de arestas é no máximo o número de pares mais o tamanho do emparelhamento. Com 10 vértices: 45 pares mais no máximo 5 arestas de emparelhamento dão 50, portanto no máximo 25 arestas. Para todo n, essa soma dá exatamente o dobro do teto de Mantel.
O lema em si é uma contabilidade cuidadosa. Uma não aresta é crítica se um único caminho de dois passos liga suas extremidades, como acontece com todas as doze não arestas da Figura 1. Os autores associam cada não aresta crítica às duas arestas de seu caminho e dividem a teia resultante em pedaços conexos. Um pedaço contém no máximo uma aresta a mais do que não arestas críticas, e cada pedaço com esse excedente precisa ser pago por uma não aresta não crítica. Para encontrá-las, os autores usam saídas por troca (switch exits): pegue uma aresta ou não aresta crítica do pedaço e troque uma de suas extremidades pelo parceiro dessa extremidade no emparelhamento. Cada não aresta não crítica é reivindicada no máximo duas vezes, cada pedaço excedente faz pelo menos duas reivindicações, e a conta fecha.
Quem encontrou o quê
“Esta prova foi encontrada em sua maior parte por IA, especificamente pelo GPT-5.6 Sol, em 11 de agosto de 2026”, escrevem os autores numa breve declaração sobre o uso de IA. O modelo encontrou uma prova completa do limite ⌊n²/4⌋, que eles simplificaram. Para um número par de vértices, ele também provou que o grafo bipartido completo equilibrado é o único caso extremo, apoiando-se num fato provado por Sumner sobre grafos em que todo emparelhamento maximal é perfeito, isto é, cobre todos os vértices.
Com um número ímpar de vértices, nenhum emparelhamento é perfeito, e muitos grafos têm todos os emparelhamentos maximais deixando de fora exatamente um vértice: o argumento do modelo não pôde ser adaptado. Os autores encontraram uma prova diferente do caso de igualdade, válida para todo n, e escreveram eles mesmos o artigo; uma última passada pelo GPT-6 Astra levou a “algumas pequenas correções”. O artigo é um preprint, ainda não revisado por pares, e não menciona nenhuma versão do argumento verificada por computador.
De volta a 1907
Se um grafo empata com o teto, a desigualdade-chave é uma igualdade para todo emparelhamento maximal. Escolhendo os emparelhamentos com astúcia, os autores mostram que um grafo assim ou é uma estrela — um vértice ligado a todos os outros, e nada mais — ou não tem nenhuma não aresta crítica. Num grafo diâmetro-2-crítico, toda aresta de um triângulo está em algum caminho crítico, então nenhuma não aresta crítica significa nenhum triângulo; uma estrela também não tem nenhum. Um grafo que empata é, portanto, sem triângulo, e o último passo é o teorema que a conjectura pretendia reforçar: o resultado de Mantel de 1907, que deixa o grafo bipartido completo equilibrado sozinho no teto.