一个完全图K_n是指一个有n个顶点的图，其中每两个点之间都有一条边相连。一个完全二分图是指这样一种图，图中的顶点分为两个点集L和R，L里的每个顶点都和R里的所有点相连。上图显示了一种把K_5划分为四个完全二分图的方法（分别用红蓝绿灰四种颜色来表示这四个子图）。你觉得，最少可以把完全图K_n划分成多少个完全二分图？给出一种划分方案，并证明这个数目已经不能再少了。
和你想象的一样，这个答案就是n-1。一个完全图K_n永远不可能被拆分为n-2个或更少的完全二分图。拆成n-1个是很好办的：从K_n中随便取出一个点作为L集，其余n-1个点作为R集，把这n-1条边从图中取出来形成一个完全二分图，然后继续递归地处理K_(n-1)；当规模降到K_2时，我们已经得到了n-2个二分图，并且图中就只剩下一条边了，合起来正好是n-1个完全二分图。现在的关键是，如何证明n-1个已经是最少的了？
这个证明牛B就牛B在，它根本就不是用组合数学的方法证明的。它居然是用线性代数来证明的！这可以说是我见过的最诡异的证明了。假设我们把K_n划分为了m个完全二分图，第i个二分图的左右两个点集分别记作L_i和R_i。给图中的每个顶点设置一个变量，第i个顶点上的数就记作x_i。于是呢，有
现在，让我们假设m<n-1。考虑下面这个线性方程组：
这个线性方程组的式子个数比未知量少，因此它一定有一组非零解c_1, c_2, …, c_n。既然每个L_i里面的变量和都为0了，根据前面的那个恒等式，我们得知
考虑所有c_i的和的平方，展开后有
但是，一方面，由线性方程组的第一个方程知c_i的总和为0，其平方当然也等于0；另一方面，c_i是非零解，它的平方和是大于0的。矛盾产生。
题目来源：Proofs from THE BOOK, Chapter 9
第一次来大牛blog留言就是SF……
坐坐沙发……
困
本来还想呼唤一下好几天没更新的你～～
楼上是不是M67大牛的。。
还是觉得数学公式用两种方式书写（文本和gif）
在阅读的时候有些郁闷……
我总觉得第一个有四个西格玛符号的等式是有问题的。左右两边的项数不等。从而我怀疑下面的证明。。。。。。
上图显示了一种把K_5划分为四个完全二分图的方法
把完全图K_n划分成完全二分图
这个是什么意思, 我怎么觉得有点歧义?
呵呵~~好方法~~
其实图论的不少问题都是用线性方程来解的，比如最大流问题
什么二分？？
所以，创业是什么？创业就是选择要未来，而不要现在；就是脱离多数人的正常的轨道，去选择一种特别的人生。如果你不想脱离常轨，那你就不要去创业。大家知道，马云高考考了两三年都没考上，最后终于考上了杭州师范学院的外语系，毕业以后当了五年英语老师。这就是常轨。结果他突然有一种冲动—要办企业。于是他和他太太还有另外几个人跑到北京，做了很多小买卖都不成功。后来他们跑到长城上去发誓，说一定要办成世界上最伟大的公司，仅仅过了十几年，他就成功了。他为什么成功了？因为他变得和普通人不一样了，他不再当老师了，不再朝九晚五地在课堂上讲课了，而是求人做生意了。他脱离了所有的常轨，虽死而无憾。结果，他把这件事慢慢做起来了。现在，他的公司已经成为世界上最伟大的公司。这就是他选择脱离正常轨道的结果。
我只是能看懂，完全无法想象怎么来的
博主我想知道组合数学的方法，看了书上的不太懂