Id: arxiv/2608.25153 Url: https://arxiv.org/abs/2608.25153 Tags: math.CO Score: 0 Title: The Erdős four-edge intersection problem Domain: math.CO Source: arxiv Authors: Andrzej Żak Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-25 Page: https://delphi.science/r/arxiv/2608.25153 For an $n$-vertex graph $G$ and a permutation $σ$ of its vertex set, let $σ(G)$ denote the corresponding relabelling of $G$, and put \[ I_G(σ)=|E(G)\cap E(σ(G))|. \] Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(σ)\geq k$ for every $σ$. In 1977 Erdős asked whether $f(n,4)=2n-4$, observing that $K_{2,n-2}$ gives the upper bound. We prove that, for all sufficiently large $n$, \[ f(n,4)=2n-4. \] Equivalently, every sufficiently large $n$-vertex graph with at most $2n-5$ edges has a relabelling with at most three common edges. Our proof is inspired by the…