Skip to main content
1 of 2
user36212
  • 1.7k
  • 14
  • 14

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

user36212
  • 1.7k
  • 14
  • 14