On the Erdős Five-Edge Intersection Problem

Abstract

For an $n$-vertex graph $G$ and a permutation $\pi$ of its vertex set, let \[ I_G(π)=|E(G)\cap E(G_π)|,\qquad μ(G)=\min_π I_G(π), \] where $G_{\pi }$ is the copy of $G$ obtained by relabelling every vertex $x\in V(G)$ as $\pi (x)$. Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph $G$ satisfying $\mu (G)\ge k$. Erdős recorded a construction of Mullin showing $f(n,5)\le 2n-2$ and asked whether equality holds for sufficiently large $n$. We prove that it does: \[ f(n,5)=2n-2 \] for all sufficiently large $n$. The proof strategy is a core--buffer--completion framework: it moves the few high-degree vertices into carefully chosen low-degree positions, confines the allowed overlap to this bounded part, and then relabels the sparse remainder without creating any additional common edge.

15 pages