Given two graph $G_1$ and $G_2$ (both $n$ vertices), what is the minimum number of edges I have to change(adding or deleting an edge counts as a change) in $G_1$ to obtain the graph $G_2$?
Now I understand it’s not a well-posed problem. I’m looking for an answer involving $n$ and number of edges of the graph.
I will be happy if somehow provides me an efficient algorithm to transform the graph to another, then I can try to provide bounds on this.
I was thinking about sorting the degrees and apply greedy algorithm. However, that fails if say $G_2$ has a $n-1$ clique and an isolated point. Once I’ve added edges to the first vertex of $G_1$, it’s determined which vertex is isolated. So, keeping track of such constraints seem hard.
This is a hopeless problem. It is currently unknown if one can find out in polynomial time if two graphs are isomorphic, which means there isn't probably an efficient algorithm to find out if you can do what you want by changing 0 edges!
https://en.wikipedia.org/wiki/Graph_isomorphism_problem