Consider simple graphs on the same vertex set $[n]$. For two graphs $G, H$, let $d(G, H) = \min\_{H' \sim H} |E(G) \triangle E(H')|$ — the smallest number of edge additions/removals needed to make $G$ isomorphic to $H$.


Let $D(G) = \max\_H d(G, H)$, and $S(G) = \max(|E(G)|, {n \choose 2} - |E(G)|)$. Clearly, $D(G) \geq S(G)$, attained either on $d(G, K\_n)$ or $d(G, \overline{K\_n})$.


**Question**: is $D(G) = S(G)$ for all graphs $G$? In other words, can any $G$ be made isomorphic to any $H$ in $S(G)$ edge additions/removals?


With computer search I verified this for $n \leq 7$. Outside of trivial cases $H = K\_n, \overline{K\_n}$, equality $d(G, H) = S(G)$ does not seem to hold very often: the only cases $(G, H)$ in this range of $n$ are $(K\_{1, 3}, C\_4)$ and $(C\_5, K\_{1, 4})$, and their complements. Despite this evidence, I still lack intuition for whether, or why this is always true.



Making graphs isomorphic with edge additions/removals
Yes. Suppose $G$ has density $d$ less than 1/2. Randomly reorder the vertices of $H$ and make the necessary edits to $G$ to get this particular copy of $H$.


Suppose $H$ has density $p$. The probability of editing a given edge of $G$ is $1-p$, and of editing a non-edge is $p$. So by linearity of expectation we edit a $d(1-p)+(1-d)p$ fraction of pairs. This function is maximised at $p=1$, when we get precisely $S(G)$ edits.


Incidentally, this is also why the trivial case is the only possibility unless $d=1/2$.


