1回の操作において、選んだ辺が結ぶ2頂点の値の総和は不変です。もっと言えば、選んだ辺を含む連結成分の値の総和は不変です。

したがって、操作後の各頂点の値を \(b_i\) にするには、各連結成分 \(C\) について

\[ \displaystyle \sum_{v \in C} a_v= \sum_{v \in C} b_v\]

となる必要があります。実はこれを満たすとき、適切に操作することで必ず各頂点の値を \(b_i\) にできることが示せます。以下ではその証明を述べます。

まず、数学的帰納法を用いて、 \(1\) 以上の任意の整数 \(N\) について(★)「\(N\) 頂点の木と長さ \(N\) の数列 \(a,b\) が与えられ、1.を満たしているときに適切な操作をすることで各頂点の値を \(b_i\) にできる」ことを示します。

\(N=1\) のときは1.の条件から \(a_1=b_1\) が満たされているので、操作回数 \(0\) 回で達成できます。

\(N=K\) のときに(★)が成り立っているとします。このとき、\(N=K+1\) について(★)が成り立つことを示せばよいです。 いま、\(K+1\) 頂点の木と長さ \(K+1\) の数列 \(a,b\) が与えられ、(1)を満たしているとします。

木の中から適当な葉をとります。とった葉を \(l\) とし、この葉と辺で結ばれている頂点を \(m\) とします。\(l\) と \(m\) を結ぶ辺を操作で複数回選び、\(a_l\) を \(+b_l-a_l\) , \(a_m\) を \(+a_l-b_l\) します。この操作の結果、頂点\(l\) 以外の \(a\) の総和と \(b\) の総和は等しくなります。

※これは、(★)の仮定から \(a\) の総和と \(b\) の総和が一致していることと、操作の結果 \(a_l = b_l\) となることから言えます。

この操作のあと、木から \(l\) を除いた部分グラフを考えます。\(l\) は葉だったので、この部分グラフはまた木になります。さらに、この木の頂点数は\(K\) で、かつ \(a\) の総和と \(b\) の総和が等しくなっています。 したがって帰納法の仮定を使うことにより、\(l\) 以外の各頂点 \(v\) についてその値を \(b_v\) とすることができます。 頂点 \(l\) の値は既に \(b_l\) にしていたので、以上から \(N=K+1\) においても(★)が満たされることが言えました。

さて、以上の議論から分かったのはグラフが木の場合に(1)が十分条件となることです。与えられるグラフが木でない場合は、まず連結成分ごとに分解し、各連結成分ごとにその連結成分に含まれる(その連結成分内での)全域木を取り出せば、グラフが木の場合に帰着できます。