Color the roads of the old scheme by red and the roads in the new scheme by green and remove all roads that are common for both schemes. Thus, we have a graph $G$, all edges of colored green or red, each vertex is incident with equal number of red and green edges (possibly zero). We want to cancel(remove) all colored edges using the following rule: $(*)\,\,\,\,\,\,\,\,\,\,$For any four vertices $v_1v_2v_3v_4$ for which $v_1v_2$ is red(green), $v_2v_3$ - green(red), $v_3v_4$ - red (green), and the last $v_4v_1$ - green (red), we can delete all those edges. If $v_4v_1$ is not an edge then we delete the other $3$ edges, connect $v_4v_1$ and color it with the opposite color as the former $v_2v_3$. Note that after applying the rule $(*)$ the new graph also has the property each vertex is incident with equal number of red and green edges. Now, to cancel all colored edges, we start from a vertex, $v_1$ , go to another vertex $v_2$ through a red edge, then exit $v_2$ through green one and so on till stop at $v_{2k}$ for which either $v_{2k}v_1$ is green, or it doesn't exist (as an edge). It's easy to see that there exist $4$ consecutive vertices $v_i, v_{i+1},v_{i+2},v_{i+3},v_{i+4}$ (here $v_{2k+j}= v_j$) for which we can apply rule $(*)$. After that, the number of (colored) edges will drop at least by $2$. That's why, finally there will be no edges and we transfer to the new scheme.

dgrozev wrote: Note that after applying the rule $(*)$ the new graph also has the property each vertex is incident with equal number of red and green edges. Now, to cancel all colored edges, we start from a vertex, $v_1$ , go to another vertex $v_2$ through a red edge, then exit $v_2$ through green one and so on till stop at $v_{2k}$ for which either $v_{2k}v_1$ is green, or it doesn't exist (as an edge). It's easy to see that there exist $4$ consecutive vertices $v_i, v_{i+1},v_{i+2},v_{i+3},v_{i+4}$ (here $v_{2k+j}= v_j$) for which we can apply rule $(*)$. After that, the number of (colored) edges will drop at least by $2$. That's why, finally there will be no edges and we transfer to the new scheme. Dear $\mathbf{dgrozev}$, how do we create this cycle $v_1v_2 \cdots v_{2k}$ in a way so that the vertices are distinct? For example, if $v_i = v_{i+3}$ then it is prohibited to apply the operation on $v_i, v_{i+1}, v_{i+2}, v_{i+3}$ (since I think loops are not allowed?). As an example, let's consider the graph on $5$ vertices $v_1, v_2, v_3, v_4, v_5$ where $v_1v_2, v_2v_3, v_3v_1, v_1v_4, v_4v_5, v_5v_1$ are red, green, red, green, red, and green respectively. Then, when you create the cycle starting at $v_1$, you would go through a red edge to $v_2$, go through a green edge from $v_2$ to $v_3$, but then go through a red edge from $v_3$ back to $v_1$. Thanks!

Yeah, I see, I was a bit hasty, sorry. But such configuration $v_1,v_2,\dots, v_{2k}$ indeed exists and the idea works. It just needs to consider a couple of additional cases. For example, it's possible the only red edge that exits $v_{2k-1}$ is a red one and it connects $v_{2k-1}$ with $a_1$. But then there is another green edge exiting $a_1$ and we can consider where it goes and after some case chasing to find what we want. In your example consider $v_4v_3$. It it's red (or doesn't exist) the required configuration is $v_1,v_2,v_3,v_4$. If it's green, $v_1,v_3,v_4,v_5$ does the job - $v_1v_3, v_4v_5$ are red, $v_1v_5, v_3v_4$ - green.

It is wellknown。and we claim that for any graphG,if $G$ can restructing to $F$,thus we have $d_{G}(x)=d_{M}(x)$

I mean $d_G(x)=d_F(x)$

@dgrozev After each restructing the resulting graph should be simple according to the problem. The solution in #2 seems incomplete because there could be multi edges. The green and red edges $v_1v_4$ might have been deleted before, then deleting $v_1v_2, v_2v_3,v_3v_4$ and adding $v_4v_1$ would not be possible.

Ok, you are right. But, this process of canceling edges, etc, should be viewed only as auxiliary process. Let $G_1,G_2,\dots,G_n$ be a sequence of graphs, each colored in two colors, and $G_i\to G_{i+1}$ corresponds to one of the two operations applied (as in #2). Let $G_n$ be the empty graph, no edges colored. One may use backward induction to prove the following claim: For each $j=1,2,\dots,n-1$ let $G_{j,1}$ be the graph consisting of the only red edges of $G_j$ and $G_{j,2}$ - the graph of the green edges. Then there is a sequence of operations complying to the original problem statement which transforms $G_{j,1}$ into $G_{j,2}$. It's obviously true for $G_{n-1}$, so we can prove it backwards for $n-2,n-3,\dots$. But, there is another another issue. The two schemes of roads may have common roads. As said in #2 we remove them. This removal is only in our minds, it may hinder applying the second operation: " if $v_4v_1$ is not an edge then we delete the other $3$ edges, connect $v_4v_1$ and color it with the opposite color as the former $v_2v_3$" since actually $v_4v_1$ could be one of those common edges that was "removed". But it can be also overcome.

Bump bump