{"id":"arxiv/2608.13071","url":"https://arxiv.org/abs/2608.13071","tags":["math.CO"],"score":0,"title":"On the Erdős Five-Edge Intersection Problem","domain":"math.CO","source":"arxiv","authors":["Chengrui Fang","Jianfeng Hou"],"reviews":0,"subject":"math.CO","summary":"For an $n$-vertex graph $G$ and a permutation $π$ of its vertex set, let \\[ I_G(π)=|E(G)\\cap E(G_π)|,\\qquad μ(G)=\\min_π I_G(π), \\] where $G_π$ is the copy of $G$ obtained by relabelling every vertex $x\\in V(G)$ as $π(x)$. Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph $G$ satisfying $μ(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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-13","reactions":{}}