网上资料比较少，所以我来补充一下。

本文主要证明：对无向连通图 $G(V,E)$ 的任意生成树 $T$，给每条非树边分配一位，每条树边用长为 $m-n+1$ 的二进制数表示（覆盖这条边的非树边为 $1$，其余为 $0$），那么删掉一组边集后图不连通当且仅当这些二进制数在异或运算下线性相关。

一句话解释：图的回路空间和割空间互为正交补。而以下是面向不懂线性代数的读者的叙述。

• 定义 $E' \subseteq E$ 是回路，当且仅当每个点都与偶数条 $E'$ 中的边相邻。回路显然对边集异或 $\oplus$ 封闭，因此回路集合可看成 $F_2$ 上的线性空间，称为回路空间 $\mathcal C$。

• 定义 $E' \subseteq E$ 是割，当且仅当 $\exists S(E') \subseteq V$ 使 $E' = \{(u,v) | u \in S(E'),v \in V-S(E')\}$。容易验证，可以取 $S(E_1 \oplus E_2)=S(E_1) \oplus S(E_2)$，因此割集也可看成 $F_2$ 上的线性空间，称为割空间 $\mathcal D$。

• $E$ 自然也可看成 $F_2$ 上的线性空间。

显然，删掉一组边集 $E_1$ 后图不连通，当且仅当 $\exists E_2 \subseteq E_1$ 使得 $E_2 \in \mathcal D$。因此只需证，像命题中一样分配二进制数后，$E_2 \in \mathcal D$ 当且仅当 $E_2$ 中的边异或和为 $0$。

1. 一条非树边 $(u,v)$ 与 $T$ 上 $u \leadsto v$ 的路径的并称为 $\langle G,T \rangle$ 的一只基环，所有 $m-n+1$ 只基环构成 $\mathcal C$ 的一组基。

   证明：

   • 由于一条非树边仅在一只基环中出现，因此所有基环线性无关。

   • 我们对回路所含非树边数量 $c$ 归纳证明所有回路均可被基环线性表出。$c=0$ 时，唯一的回路是 $\varnothing$；$c>0$ 时，随便异或一只基环后 $c \gets c-1$ 递归即可。

2. 任取根将 $T$ 看成有根树，$T$ 的一棵子树 $T_1$ 与 $V-T_1$ 之间的边称为一只基础割，所有 $n-1$ 只基础割构成 $\mathcal D$ 的一组基。

   证明：

   • 由于一条树边仅在一只基础割中出现，因此所有基础割线性无关。

   • 我们对割所含树边数量 $d$ 归纳证明所有割均可被基础割线性表出。$d=0$ 时，唯一的割是 $\varnothing$；$d>0$ 时，随便异或一只基础割后 $d \gets d-1$ 递归即可。

3. 对于边集 $E_1,E_2$，定义点积 $\langle E_1,E_2 \rangle=\lvert E_1 \cap E_2 \rvert \bmod 2$，那么 $\forall c \in \mathcal C,d \in \mathcal D$，有 $\langle c,d \rangle=0$。

   证明：

   • 定义一个点的度数是其属于 $c$ 的邻边数，这是一个偶数。

   • 考虑 $S(d)$ 中点度数和 $s$：两端同属 $S(d)$ 或 $V-S(d)$ 的边，若不属于 $c$ 则被计算 $0$ 次，否则被计算 $2$ 次；其余边被计算恰 $1$ 次。因此 $\langle c,d \rangle \equiv s \equiv 0 \pmod 2$。

4. $x \in \mathcal D$ 当且仅当 $x$ 与所有基环点积为 0。

   证明：

   • 与所有基环点积为 0 是由 $m$ 个变量和 $m-n+1$ 条方程组成的齐次线性方程组，这些方程线性无关，因此其解空间维度为 $m-(m-n+1)=n-1$，而 $\mathcal D$ 属于此解空间且维度恰为 $n-1$。

原命题中所赋二进制数就是一条边与所有基环的点积，这就不难看出其正确性了。

练习：

1. 如何判断删掉 $k$ 个点后图的连通性？

2. 和欧式空间不同，这里的空间不能写成一个子空间与其正交补的直和。例如，$C_4$ 的整个边集既是回路也是割。试证明：一个连通图的边空间是回路空间与割空间的直和，当且仅当其生成树数量为奇数。

参考文献：

1. On the Parity of Graph Spanning Tree Numbers, David Eppstein, 1996