The Erd\H{o}s four-edge intersection problem

Abstract

For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put \[ I_G(\sigma)=|E(G)\cap E(\sigma(G))|. \] Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In 1977 Erd\H{o}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 recent work of Fang and Hou on the Erd\H{o}s--Mullin five-edge intersection problem and builds on their core--buffer and absorption framework. The main additional ingredients are a growing high-degree core $C$ satisfying \[ |C|\Delta(G-C)=o(n), \] and a rigidity analysis of the equality case in the relevant first-moment estimate. This analysis shows that the only core--buffer configuration forcing four local common edges is of $K_{2,|C|}$ type; the strict bound $e(G)\leq2n-5$ then supplies a defect which breaks this configuration.