Making graphs isomorphic with edge additions/removals

Question

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.

Answer 1

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$.