graph - 有向图的一个性质

Question

请帮我解决这个问题：

给出一个弱连通的简单有向图 G。证明 S = sum(abs(degIn(u)-degOut(u))) 是偶数。

非常感谢。

Answer 1

显然，这个陈述对于任何没有边的图 G 都是正确的。

假设 G 是一个至少有一条边的图。令 e = (u, v) 为 G 中的任意边。假设 G - e 满足性质。现在检查 G。在 G - e 和 G 之间，对于除 u 和 v 之外的所有顶点，abs(degin(w) - degout(w)) 的值保持不变。u 和 v 的值都恰好变化 1，对于 -2、0 或 2 的总变化。因此，对于 G，sum(abs(degin(w) - degout(w)) 是偶数。

通过对 G 中的边数进行归纳，所有图 G 都满足该性质。