Graham-Pollak定理的证明

一、定理陈述

Graham - Pollak定理：任何$K_n$（完全图，有$n$个顶点）的分解中至少需要$n - 1$个完全二部图。

二、符号定义

1. 对于图中的每个顶点$v_i \in V$，定义一个实变量$x_i$，其中$V$是图中所有顶点的集合。
2. 对于第$k$个二部图，将其左侧顶点集记为$L_k$，右侧顶点集记为$R_k$。
3. 对于任意顶点集$S$，定义$X(S)=\sum_{v_i \in S} x_i$，即$S$中顶点对应的变量之和。

三、用变量表示图的边

1. 完全图$K_n$的边可以表示为$\sum_{1\leq i < j\leq n}x_ix_j$。
2. 因为二部图$k$覆盖了完全图的边，所以有$\sum_{1\leq i < j\leq n}x_ix_j=\sum_{k}X(L_k)X(R_k)$。

四、构建线性方程组

1. 考虑线性方程组$X(V) = 0$和$X(L_k)=0$，$X(R_k)=0$对每个$k$成立。
2. 对于任意满足上述线性方程组的解，有：
   • $0 = X(V)^2=\left(\sum_{i}x_i\right)^2=\sum_{i}x_i^2 + 2\sum_{1\leq i < j\leq n}x_ix_j$。
   • 由$\sum_{1\leq i < j\leq n}x_ix_j=\sum_{k}X(L_k)X(R_k)$，可得$0=\sum_{i}x_i^2+ 2\sum_{k}X(L_k)X(R_k)$。

五、矛盾推导

1. 注意到$\sum_{i}x_i^2$是实变量的平方和。
2. 对于实变量的平方和，只有当所有变量都为零时，其和才为零。
3. 如果使用的二部图数量少于$n - 1$，则线性方程组中的方程数量少于变量数量（变量数量为$n$，方程数量少于$n$）。
4. 根据线性代数知识，这样的齐次线性方程组会有非零解。
5. 但如果存在非零解，就会导致$\sum_{i}x_i^2 = 0$的矛盾（因为非零解意味着至少有一个$x_i$不为零，平方和就不可能为零）。

六、结论

因此，为了避免这种矛盾，完全图$K_n$的分解中至少需要$n - 1$个完全二部图，这就证明了Graham - Pollak定理。