A new mathematical result puts an exact asymptotic price on a simple-sounding graph challenge. For every sufficiently large n, the minimum number of edges needed to ensure that every relabelling leaves at least four edges in common with the original graph is f(n,4)=2n−4.
The same result can be read from the other direction. Every sufficiently large n-vertex graph with at most 2n−5 edges has some permutation of its vertices that shares at most three edges with the original graph. In other words, below the 2n−4 mark, four common edges are not unavoidable.
The qualification matters: “sufficiently large” is not quantified in the preprint. The theorem does not say that the formula already holds for every value of n.
The puzzle behind the formula
The question concerns finite simple graphs and permutations of their vertex sets. Given a graph G, a permutation σ relabels the vertices; I_G(σ) records the edges shared by G and its relabelled copy. The function f(n,k) is the smallest edge count for which I_G(σ) is at least k for every permutation σ.
For k=4, the problem asks how sparse a graph can be while still making a four-edge overlap unavoidable, regardless of how its vertices are renamed.
The graph K2,n−2 supplies the upper bound f(n,4)≤2n−4. The theorem’s lower-bound side says that an n-vertex graph with 2n−5 edges or fewer can be relabelled to bring the overlap down to three or fewer, once n is sufficiently large.
Inside the proof
The proof combines several pieces of graph theory. It uses uniformly random permutations and a first-moment argument, an expectation-based estimate, to obtain a general graph bound.
It also uses list packing, in which edges of one graph must map to non-edges of the other while forbidden vertex-to-image pairs are avoided. The target is a relabelling with only a small number of common edges.
A core-buffer framework organizes the rest. The proof replaces a fixed finite core with a growing core C satisfying |C|=o(n) and |C|Δ(G−C)=o(n). Put simply, the core and the core-size times outside maximum-degree quantity both grow more slowly than n.
A degree-deficit lemma supplies a lower bound for the buffer. An absorption lemma then extends a prescribed partial permutation to a full permutation while keeping the number of common edges at at most three.
The proof separately checks the rigid exception: the only core-buffer configuration identified as capable of forcing four local common edges is of K2,|C|-type. The strict edge condition e(G)≤2n−5 excludes that configuration.
What remains open
The final step is a contradiction argument. It assumes an infinite sequence of counterexamples, each with at most 2n−5 edges but with at least four common edges under every permutation. After excluding all possible subsequences, the paper concludes that every sufficiently large graph under the edge bound has a relabelling with at most three common edges.
That closes the asymptotic argument, but leaves a finite-size question. The preprint does not identify the smallest n for which f(n,4)=2n−4, and it does not claim the equality for every n.
The document is an arXiv version 1 preprint dated 25 August 2026.
The author reports partial support from the Polish Ministry of Science and Higher Education.
The manuscript says generative artificial intelligence tools assisted with exposition and with developing and drafting parts of the proof. It also says the author checked and revised the mathematical statements and proofs.
Paper data and sources
Original title: The Erdős four-edge intersection problem
Authors: Andrzej Żak
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text