设 T 是非平凡树。证明
(a) T 是 2 部图
(b) 设 ${X,Y}$ 是 T 的 2 部划分，则
(i) 若 $|X|\ge|Y|$，则 $X$ 中至少有 1 个 1 度点
(ii) 若 $|X|=|Y|+k$，则 $X$ 中至少有 $k+1$ 个 1 度点
$T$ 不含奇圈，所以 T 是 2 部图
证 (ii) 即可
设 X 中 1 度点全体为 $X_1$，则 $X-X_1$ 中点度均 $\ge 2$，则
$$
|X_1|+2(|X|-|X_1|)\le\sum_{x \in X} d_T(x) = e(X,Y)=e(T)=n-1
$$
其中 $n=|X|+|Y|=2|X|-k$ 为 T 的点数，代入可得 $|X_1|\ge k + 1$
$\mathcal{A}={A_1,\dots,A_n}$ 是 $X={1,\dots,n}$ 的 n 个不同子集族，证明：存在 $x\in X$ 使得 $A_1\cup {x},A_2\cup {x}，\dots,A_n\cup {x}$ 互不相同。
$\mathcal{A}$ 中元素互不相同，则它们的补集 $\bar{A}_1,\bar{A}_2,\dots,\bar{A}_n$ 也互不相同，根据 Bondy's Theorem，$\exist x \in X$，使得 $\bar{A}_1 \backslash {x},\bar{A}_2 \backslash {x},\dots,\bar{A}_n \backslash {x}$ 互不相同，则它们的补集 $A_1\cup{x},A_2\cup{x},\dots,A_n\cup{x}$ 互不相同，此 $x$ 即为所求。
证明：设 $B_1$ 和 $B_2$ 是键，则 $B_1\triangle B_2$ 是边割集，因而含键
$B_1\triangle B_2=B_1\cup B_2 - B_1\cap B_2$
设 $B_1=[S,\bar{S}]$，$B_2=[T,\bar{T}]$，设 $W=S\cap T$，$X=S\cap \bar{T}$，$Y=\bar{S}\cap T$，$Z=\bar{S}\cap \bar{T}$
则 $B_1=[W,Y]\cup[W,Z]\cup[X,Y]\cup[X,Z]$，$B_2=[W,X]\cup[W,Z]\cup[X,Y]\cup[Y,Z]$，则 $B_1\triangle B_2=[W,Y]\cup[W,X]\cup[Z,Y]\cup[Z,X]$
可知 $B_1\triangle B_2$ 是 $X\cup Y$ 与其补集 $W\cup Z$ 之间的边割集
设 $K$ 为从连通图 $D$ 关联矩阵 $M$ 中删去任意一行得到的矩阵，则 $K$ 是割空间 $\mathcal{B}(D)$ 的基矩阵
$\dim (\mathcal{B}(D))=n-1$，且 $\mathcal{B}(D)$ 是 $M$ 的行向量空间 $\mathcal{M}$，故 $\text{rank} \mathcal{M} = n-1$。设 $M$ 的行向量为 ${\beta_1,\dots,\beta_n}$，不妨设 $K$ 的行向量为 ${\beta_1,\dots,\beta_{n-1}}$，又 $\beta_{n}=-(\beta_1+\dots+\beta_n)$，则 ${\beta_1,\dots,\beta_{n-1}}$ 线性无关，故 $K$ 是割空间 $\mathcal{B}(D)$ 的基矩阵。
设 $C$ 是 $D$ 中的圈，$B$ 是 $D$ 中的键，证明：
(a) $\pmb{f}_C\in \mathcal{E}(D)$ 是 $D$ 的圈向量，$D$ 的所有圈向量构成 $\mathcal{E}(D)$ 的子空间
(b) $\pmb{g}_B\in \mathcal{E}(D)$ 是 $D$ 的割向量，$D$ 的所有割向量构成 $\mathcal{E}(D)$ 的子空间
$\forall x \notin V(C)$，有 $f_C^+(x)=f_C^-(x)=0$。
$\forall x\in V(C)$，与其关联的圈 $C$ 上的边为 $a_1$ 和 $a_2$
- 两者同于圈定向，则 $f_C^+(x)=f_C^-(x)=1$
- 两者不同于圈定向，则 $f_C(a_1)$ 和 $f_C(a_2)$ 其中一个是 1，另一个是 -1，以 x 同为起点或终点，则有 $f_C^+(x)=f_C^-(x)=0$
因此 $\forall x \in V(D),f_C^+(x)=f_C^-(x)$
$\forall \pmb{f}_1,\pmb{f}_2 \in \mathcal{C}(D),\forall x \in V(D), \forall \lambda,\mu \in \mathbb{R}$，有
$$
\begin{aligned}
(\lambda \pmb{f}_1+\mu\pmb{f}_2)^+(x)
&= \lambda \pmb{f}_1^+(x) +\mu\pmb{f}_2^+(x)\
&= \lambda \pmb{f}_1^-(x) +\mu\pmb{f}_2^-(x)\
&= (\lambda \pmb{f}_1(x) +\mu\pmb{f}_2)^-(x)\
\end{aligned}
$$
则 $\lambda \pmb{f}_1+\mu \pmb{f}_2 \in \mathcal{C}(D)$
故 $\mathcal{C}(D)$ 是 $\mathcal{E}(D)$ 的子空间
$\forall a=(x_1,x_2)\notin B$，$x_1$ 和 $x_2$ 要么同属于 $S$，要么同属于 $\bar{S}$，此时 $\pmb{p}(x_1)=\pmb{p}(x_2)$，则 $\delta_{\pmb{p}}(a)=\pmb{p}(x_1)-\pmb{p}(x_2) = 0 = \pmb{g}_B(a)$
$\forall a=(x_1,x_2) \in (S,\bar{S})$，$\pmb{p}(x_1)=1$，$\pmb{p}(x_2)=0$，则 $\delta_{\pmb{p}}(a)=\pmb{p}(x_1)-\pmb{p}(x_2)=1=\pmb{g}_B(a)$。
$\forall a=(x_1,x_2) \in (\bar{S},S)$，$\pmb{p}(x_1)=0$，$\pmb{p}(x_2)=1$，则 $\delta_{\pmb{p}}(a)=\pmb{p}(x_1)-\pmb{p}(x_2)=-1=\pmb{g}_B(a)$。
所以 $\pmb{g}B=\delta{\pmb{p}}$ 是割向量
$\forall \pmb{g}_1,\pmb{g}_2 \in \mathcal{B}(D),\forall a=(x_1,x_2) \in E(D), \forall \lambda,\mu \in \mathbb{R}$，有
$$
\begin{aligned}
(\lambda \pmb{g}_1+\mu\pmb{g}_2)(a)
&= \lambda \pmb{g}_1(a) +\mu\pmb{g}_2(a)\
&= \lambda \pmb{p}_1(x_1) - \lambda \pmb{p}_1(x_2) + \mu\pmb{p}_2(x_1) - \mu\pmb{p}_2(x_2)\
&= (\lambda \pmb{p}_1(x) +\mu\pmb{p}_2)(x_1)-(\lambda \pmb{p}_1(x) +\mu\pmb{p}_2)(x_2)\
\end{aligned}
$$
则 $\lambda \pmb{g}_1+\mu\pmb{g}_2 \in \mathcal{B}(D)$
故 $\mathcal{B}(D)$ 是 $\mathcal{E}(D)$ 的子空间
