On the Erd\H{o}s Five-Edge Intersection Problem

Abstract

For an $n$-vertex graph $G$ and a permutation $\pi$ of its vertex set, let \[ I_G(\pi)=|E(G)\cap E(G_{\pi})|,\qquad \mu(G)=\min_{\pi} I_G(\pi), \] 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\H{o}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.