Graham-Pollak Theorem

문제

(Graham, Pollak 1972) Prove that the edge set of \(K_n\) cannot be partitioned into the edge-disjoint union of less than \(n-1\) complete bipartite subgraphs. Also, prove that this bound is tight.

스포 방지선

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

(증명) \(K_n\)의 각 정점을 \(1, 2, \cdots , n\)이라 하자. 우선 \(n-1\)개의 완전 이분 그래프로 \(K_n\)을 분할하는 것은 쉽다. 

귀류법으로, 완전 이분 그래프 \(B_1 , B_2, \cdots B_m \)이 \(K_n\)을 분할한다고 하자. (단, \(m \le n-2\)다.)

또한, 각 완전 이분 그래프 \(B_k\) 안에서 두 disjoint independent set을 \(L_k, R_k\)라고 부르자.

즉, \(B_k\)의 간선은 \(L_k\)의 정점과 \(R_k\)의 정점 사이를 모두 연결한 것이다.

다음 조건을 만족하도록 \(K_n\)의 정점 \(v\)에 실수 \(x_v\)를 놓자. 

조건 1: 모든 \(1 \le k \le m\)에 대하여, \( \displaystyle \sum_{v \in L_k} x_v = 0 \)이고, \(\displaystyle \sum_{v=1}^n x_v = 0\) 

조건 2: \(\displaystyle \sum_{v=1}^n x^2_v \neq 0 \)이다. 즉, 모든 \(v\)에 대해 \(x_v\)가 전부 \(0\)은 아니다.

이것이 가능함을 보이자. 기초적인 선형대수학을 알면 쉽게 보일 수 있다.

조건 1은 식의 개수가 \(m+1\)개인 하나의 Homogeneous한 연립방정식을 이룬다. 

변수의 개수가 \(n\)개이고 \(m+1 < n\)이므로, 이 연립방정식은 non-trivial 해를 가진다. 

그러므로 조건 1, 2를 만족하도록 정점 \(v\)에 실수 \(x_v\)를 놓을 수 있다. 

이제 \(B_1 , B_2, \cdots B_m \)이 \(K_n\)의 edge set을 완벽하게 분할하므로, 다음 식이 성립한다.

$$ \sum_{1 \le i < j \le n} x_ix_j = \sum_{k=1}^m \left(\displaystyle \sum_{i \in L_k} x_i \right) \cdot  \left(\displaystyle \sum_{j \in R_k} x_j \right) $$

이제 조건 1에 의해, 우변은 \(0\)이다. 그러면 결국 \( \displaystyle \sum_{1 \le i < j \le n} x_ix_j = 0\)인데, 다시 조건 1에서 \( \displaystyle \sum_{v=1}^n x_v = 0 \)이다.

이 식을 제곱하고 정리하면 \(\displaystyle \sum_{v=1}^n x^2_v = 0 \)을 얻고, 이는 조건 2와 모순이다. \(\blacksquare\)