以下问题部分选自单墫老师的《趣味的图论问题》（最近看这本书看得入迷），还有一些是经典问题，这本书确实很好看，值得看一看...

1.十个学生参加一次考试，试题十道。已知没有两个学生做对的题目完全相同。证明：在这十道试题中可以找到一道试题，将这道试题取消后，每两个学生所做对的题目仍然不会完全相同。

    用反证法。如果不管取消哪一道试题，都会出现两个学生做对的题目完全相同，则将10个学生看成10个顶点，任取一对除第一题之外做对题目完全相同的学生，连一条编号为1的边，对其它题同理，得到一个10条边的图，每条边的编号不相同，并且显然每两个顶点之间最多只有一条边。这个图一定是有圈的（否则它最多有9条边），圈中每条边的编号不相同，从圈上一点开始，沿着圈走，每过一条边就相当于更改一道题的对错，这样走回原来的点，做对题目的情况与原来不同，这显然是不可能的。

2.有一个n行m列的矩阵，n*m个实数互不相同，先在每一行中挑出最大数，把这n个最大数的最小值记为A，再在每一列中挑出最小数，把这m个最小数的最大值记为B，问能否确定A,B的大小。

    不管这些数的大小关系如何，一定有A>B。A,B都是矩阵中确定位置上的数，如果A,B在同一行或同一列，根据选出A,B的方法，显然有A>B，如果A,B既不在同一行，也不在同一列，则一定能挑出一个数C，使得C与A同一行，C与B同一列，就有A>C>B。

3.对于含有2n（n为正整数）个顶点的简单图，若图中没有三角形，求边数的最大值。

    将顶点分为两组，每组含有n个顶点，在两个不在同一组的顶点间连一条边（或者说构造完全二分图K(n,n)），可以连出n^2条边，而任取三个顶点必有两个顶点在同一组，它们没有边相连，因此不会构成三角形。

下面用数学归纳法证明，n^2不能换成更大的数。当n=1时，显然最多可以连出1条边，设n=k-1时，最多可以连出(k-1)^2条边，当n=k时，图中至少有一条边，去掉这条边的两个端点a,b，最多有(k-1)^2条边，如果加上a,b，则原来的2(k-1)个点显然每一个点最多与a,b连一条边（否则它与a,b构成一个三角形），算一下总边数就是：

(k-1)^2+2(k-1)+1=k^2。结论证完了。

    对于顶点数为奇数2n+1的情况，用类似的方法可以证出最多有n^2+n条边。

4.甲乙玩开车旅行的游戏，先选定一个地图（即简单图G，注意可能不是平面图），甲选定一个顶点作为开车的起点，乙沿着一条边将车开到相邻的顶点，甲再沿另一条边把车开到新的顶点，已经去过的顶点（包括起点）就不能再去了，谁没边可走谁就输了。问甲必胜的充要条件是什么？

    当且仅当图G不存在完全匹配时，甲必胜。一个匹配是指从图G中选出的一些无公共端点的边（这相当于图G的顶点两两配对），如果所有顶点都属于匹配中某一条边的端点（这相当于每一个顶点都配上了对），则称为完全匹配。

    先讨论图G存在完全匹配的情况，也就是所有点都被两两配对，不管甲开到哪，乙都把车开到与当前位置配对的点，最后走投无路的肯定是甲。

    如果图G不存在完全匹配，则找到一个图G的最大匹配（含有边数最多的匹配，如果有多个则任选一个），甲随便选择一个没有被匹配的点作起点，然后不管乙开到哪，甲都照着选定的最大匹配开。

    下面证明，乙不可能开到一个没有被匹配的点。假如出现这种情况，则考察之前开车的路径，甲沿着最大匹配走，乙走的边都没被匹配，最后结果一定是：在最大匹配上的边与没在最大匹配的边交替出现，并且第一条边和最后一条边都没在匹配中，并且起点和终点都没被匹配。把这条路上所有没匹配的边换成匹配过的边，把原来匹配过的边去掉，结果就是多了一条匹配边。这与原来匹配的最大性矛盾。事实上，这条路径就是所谓的增广路，在求取最大匹配时常用找增广路的方法。

5.在8*8的国际象棋盘的64个格子中取16个格子。证明：如果每一行与每一列都恰好取了两个格子，那么一定可以把8个红棋与8个蓝棋放在这些取定的格子里，使得每一行与每一列都恰有一个红棋与蓝棋。

    以格子为顶点，如果两个格子在同一行或同一列，就在这两个格子间连一条边，显然这个图的圈都是横竖边交替，所以圈长均为偶数，于是这个图是二分图，只需一组顶点放红棋，另一组顶点放蓝棋即可。

    这里利用了一个小结论：圈长均为偶数的简单图是二分图。如果图不连通，可以分别考虑每一个连通分支，问题化为连通图的情况。选定一个顶点s染为黑色，对于其它顶点，它到s至少有一条链（因为是连通图），并且如果有多条链，它们一定是同奇偶的（否则就出现长为奇数的圈），若链长为奇数则染为白色，否则染为黑色，显然相邻的两个点必定一黑一白。把顶点按染上的颜色分为两组即得此图为二分图。

    有趣的是，这个条件也是必要的。如果一个图是二分图，其中一组顶点染黑，另一组顶点染白，则任意一个圈上的顶点必定黑白交替，长度必为偶数。

6.平面上n条直线将平面分成很多部分，证明：可以将每一部分染上黑色或白色，使得有公共边（线段或射线，但只有公共点的不算）的两块区域颜色不同。

证法1：

    先不考虑直线，设此时整个平面为白色，现在逐一添加直线，每添加一条直线，都将直线的其中一边进行“反色”（黑变白，白变黑），显然新产生的“有公共边的两个区域”中的公共边是这条直线的一部分，这两个区域原来属于同一个区域，颜色相同，反色后颜色不同。添加到最后，就得到了一种满足要求的染色方案。

证法2：

    以区域为顶点，如果两个区域有公共边，则在两区域间连一条边，构成一个简单图。只要证出这个图中所有圈长均为偶数，由上一题中关于二分图的结论，这题就证出来了。在图中任取一个圈，数一下这个圈与所有直线的交点有多少个，容易看出：对每条直线，圈与直线的交点均为偶数个，于是交点的总数也是偶数，这等价于圈长为偶数。

7.n个人进行比赛，每两个人都赛过一场并分出胜负（但并不一定具有传递性，即A胜B,B胜C不能推出A胜C），证明：可以把n个人排成一排，使得每相邻两人都是左边的胜右边的。

    用数学归纳法证明。当n=2时，结论显然成立。假设当n=k时结论成立，考虑n=k+1的情况，此时在k+1个人中随意选出一个人A，根据归纳假设，可以先把剩下k个人按要求排成一排。如果A胜了第一个人，则可以把A添到最左边；如果最后一个人胜A，则把A添到最右边；如果前两种情况均不成立，即第一个人胜A，A胜最后一人，则找出最靠左的被A战胜的人，把A放到它左边就满足题意。

    如果以人为顶点，对于每两个人，从胜者向负者连一条有向边，这样形成的图称为竞赛图。

8.条件同上，证明：总存在一个人A，使得其余人要么被A打败，要么败于被A打败的一个人。

    证明很简单，赢的次数最多的人（如果有多个则任选其中一个）满足条件，如果存在另一个人既没被A打败，又没败于被A打败的人，则它赢的次数至少比A赢的次数多1，矛盾。

    另外还有一个结论：若这样的人只有一个，那么这个人打败了其它所有人。仍然用反证法，设这个人是A，假设A没有打败其它所有人，我们把打败A的人挑出来，只关心这些人之间的比赛情况，套用刚才的这个结论，一定存在一个人B，使得被挑出来的人要么被B打败，要么败于被B打败的一个被挑出来的人。而没被挑出来的人显然败于A（A是一个被B打败的人），于是B也满足要求。这违反了“这样的人只有一个”的条件。

9.亚瑟王在王宫中召见他的2n名骑士，其中某些骑士之间互相有怨仇，已知每一个骑士的仇人不超过n-1个。证明：摩尔林（亚瑟王的谋士）能够让这些骑士围着那张著名的圆桌坐下，使得每一个骑士不与他的仇人相邻。

    首先以任意顺序安排骑士，接下来我们证明可以通过调整使相邻的仇人减少。设有一对仇人A,B相邻，B在A的右边，A的朋友至少有n个，B的仇人至多有n-1个，因此一定存在两个相邻的人A',B'（B'在A'的右边），使得A和A'是朋友，B和B'不是仇人，否则的话，取出n个A的朋友，它们右边相邻的位置都是B的仇人，B的仇人个数就大于n-1个，矛盾。此时把B向右一直到A'的整个部分颠倒顺序，原来的相邻关系只是由AB,A'B'换成了AA',BB'，由至少一对仇人变为没有仇人，于是相邻的仇人对数一定严格减少了。经过有限次调整后，相邻位置上就没有仇人了。

    如果以骑士为顶点，在每对朋友间连一条边，原问题就等价于：有2n个顶点的图，若每个点的次数不小于n，则一定存在哈密顿圈，即所有顶点都恰经过一次的圈。而我们有更一般的定理：n个顶点（n≥3）的图，若任意两个不相邻的顶点的次数之和都大于等于n，那么这个图一定有哈密顿圈。证明方法类似。