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.
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 his 1977 formulati...
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$ satis...
For graphs $H$ and $F$, let $ex(n,H,F)$ be the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. We study this problem when $H$ is a clique and $F=T_t$which is a fixed tree on $t$ vertices. The Erd\H{o}s--S\'{o}s conjecture concerns the value of $ex(n,K_2, T_t)$. Gerbner and Palmer proposed a more genera...
For a graph $G$, let $\cpn(G)$ and $\ccn(G)$ denote the minimum numbers of cliques whose edge sets partition and cover $E(G)$, respectively, and put $f(n)=\max_{|V(G)|=n}\bigl(\cpn(G)-\ccn(G)\bigr).$ In 1983, Erd\H{o}s, Faudree, and Ordman asked whether there is a sequence of graphs $G_n$ such that $|V(G_n)|=n$ and $\c...
For an $F$-free graph $G$, a non-edge is $F$-saturating if adding it to $G$ creates a copy of $F$. We denote by $f_{p+1}(n,m)$ the minimum number of $K_{p+1}$-saturating non-edges in a $K_{p+1}$-free $n$-vertex graph with $m$ edges. Erd\H{o}s and Tuza conjectured that $f_4\left(n,\mathrm{ex}(n,K_3)+ 1\right)= (1 + o(1)...
For a family $\mathcal{F}$ of $k$-graphs, $\ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $\ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n...
