例10指出图（12），图（13）和图（14）中哪一个图，可以从图中的某个点出发，用铅笔不离开纸面，一笔画出整个图？
A
x
B
F
D
E
y
C
图（12）
图（13）
x
A z
w y
B F
图（14） C D
E
图（15）
解 把图（12）中圆周的交点视为顶点，其集合记V.对于顶点u，v∈V，当
且仅当交点u和v有圆弧相连接时令顶点u和v相邻，得到的是6阶图G1（图（15））.图G1中每个顶点的度都是4，由定理3，图G1具有欧拉回路.因此，可以从图（12）中的某个交点出发，按照一条欧拉回路上顶点的顺序，沿着圆弧，一笔画出整个图，最后回到原来的交点上.
把图（13）中的交点视为顶点.当且仅当交点间有线段连接时，令相应的顶点相邻，得到的图记作G2,.图G2中恰有两个3度顶点x和y，其他顶点都是偶顶点，有定理4，图G2含有一条以x和y为端点的欧拉迹，于是，从点x出发，按照这条欧拉迹中顶点的顺序，一笔画出整个图，最后到达点y.
和图（13）相似，图（14）中含有四个奇顶点x，y，z和w，因此不能一笔画出图（14）.
例11 圆周上有n个点，n>2，其中任意两点都用线段连接.能否一笔画出所
12
有这些线段，使得第一条线段的终点和第二条线段的始点相重合，第二条线段的终点和第三条线段的始点相重合，等等，而且最后一条线段的终点和最初的一条线段的起点相重合？
解 把圆周上给定的n个点视为n个顶点，任意两个顶点都相邻，得到的是一个n阶完全图Kn，Kn中每个顶点的度都是n-1，当n为奇数时，Kn中的每个顶点都是偶顶点.因此，有定理3，完全图Kn含有欧拉回路，因此，从Kn中某个顶点出发，按照这条欧拉回路上顶点的顺序，即可一笔画出整个图Kn，最后回到原来的顶点上.当n为偶数时，Kn中每个顶点都是奇顶点，由定理3和定理4，完全图Kn不含欧拉回路和欧拉迹.因此，偶数阶完全图Kn不能用一笔画出所有线段.
2.3哈密尔顿圈和哈密尔顿路在数学竞赛中的应用
哈密尔顿是十九世纪英国著名数学家.1859年，他发明了一种游戏.这种游戏使用一个实心的正十二面体，在它的二十个顶点上标注着世界上二十个著名城市的名字：阿姆斯特丹，安亚伯，柏林，布达佩斯，都柏林，爱丁堡，耶路撒冷，伦敦，墨尔本，莫斯科，新西伯利亚，纽约，巴黎，北京，布拉格，里约热内卢，罗马，旧金山，东京和华沙，要求游戏者寻找一条环路，使得从某个城市出发，能够沿着正十二面体的棱前进，经过每座城市恰好一次，然后回到原来的城市.
这种游戏可以抽象为图论问题，把正十二面体的顶点视为图G的顶点，把正十二面体的棱视为图G的边，得到一个图G.于是，此游戏相当于，在图G中寻找一条道路，使得从图G中某个顶点出发，沿着图G的边，经过图G的每个顶点恰好一次，然后回到原来的顶点，也就是寻找一个经过每个顶点恰好一次的圈.这样的圈叫做图G的哈密尔顿圈.
下面我们就来介绍一下哈密尔顿圈和哈密尔顿路的基本概念.
2.3.1哈密尔顿圈和哈密尔顿路
如果在图G中，有一个圈经过每个顶点恰好一次，那么这个图称为哈密尔顿图. 这样的圈叫做哈密尔顿圈. 如果在图G，有一条路经过每个顶点恰好一次，那么这条路称为哈密尔顿路.
哈密尔顿提出了图论研究的一个重要课题，即如何判断一个图是否是哈密尔
13
顿图.表面上看，哈密尔顿圈和一笔画很相似，其实质却迥然不同，对于图G的哈密尔顿圈C，只要求图G的每个顶点都在圈C上出现，而且只出现一次.至于图G的边，则不作任何要求，即允许在圈C上出现，也可以再圈C上不出现.对于图G的欧拉回路C*，则正相反，它要求图G的每条边都要在回路C*上出现一次，而且只出现一次，而对图G的顶点，则不计其出现与否.前面已经知道判断一个图是否是欧拉图问题已经彻底、干净的解决了.但判断一个图是否是哈密尔顿图问题，至今仍未解决.它是图论问题的一个难题，是世界各国许多图论专家所关注的研究课题之一.在这里，我只介绍一个比较简单、比较实用的定理.
定理5 设G是n阶简单图.如果对图G中任意两个不相邻顶点u和v，均有
, （3）
则图G是哈密尔顿图.
推论 图G的顶点数为
,且最小度
,G为哈密尔顿图.
2.3.2应用举例
例12 传说英国有一位国王，叫亚瑟王，在王宫中召见他的2n名骑士，其中某些骑士之间互有仇怨.已知每名骑士的仇人不超过n-1个.证明，亚瑟王的谋士摩尔林一定有办法让这2n名骑士围着圆桌入座，使得每名骑士都不和他的仇人坐在一起.（波兰数学竞赛试题）
证 用顶点表示骑士，当且仅当骑士x和y互不成仇时顶点x和y相邻，得到的2n阶简单图记作G.由于每名骑士的仇人不超过n-1个，所以图G中每个顶点的度都至少是n.由定理5的推论，图G是哈密尔顿图，即图G具有哈密尔顿圈.于是只要让这2n名骑士按照这条哈密尔顿圈的顶点顺序就座，每名骑士两旁就座的就不是他的仇人.
例13 有n个人，围圆周入座，n≥5.证明，可以调整这n个人的座位，使得每个人的两旁就座的是原来不坐在一起的人.（“祖冲之杯”邀请赛试题）
证 假设围着圆桌入座的n个人按逆时针的顺序是v1，v2，···，vn，（图（16））.把n个人v1，v2，···，vn视为n个顶点，对于顶点u，v∈V，当且仅当u和v不坐在一起时令u和v相邻，得到的是n阶简单图G.
14
v1
v2
vn
v1
v3 vn-1 v2
v5
v3
v4
图（17）
图（16）
很显然，图G中每个顶点的度是n-3.当n≥3时，n-3≥n-= 因此由定理5的推论，图G具有哈密尔顿圈.于是，只要让这n个人按照这条哈密尔顿圈上的顶点顺序就座即可.当n=5时，图G如图（17），很显然，图G具有哈密尔顿圈v1v3v5v2v4v1，此时只要让这5个人按照顶点顺序v1，v3，v5，v2，v4入座即可.
例14举行一个国际会议，有A，B，C，D，E，F，G 7个人.已知下列事实： A会讲英语； B会讲英语和汉语；
C会讲英语、意大利语和俄语； D会讲日语和汉语； E会讲德语和意大利语； F会讲法语、日语和俄语； G会讲法语和德语.
试问这7个人应该如何安排座位，才能使每个人都能和他身边的人交谈？（小学奥林匹克数学竞赛试题）
解 依据已知条件建立一个图的模型，我们用点表示人，于是得到点集V={A，B，C，D，E，F，G}.对于任意两点，若有共同语言，就在他们之间连一条线，可以得到边集E，则图G=（V，E），如图（18）：
15
A
B
C
E
D
F
G
图（18）
如何排座位使每个人都能喝他身边的人进行交谈？则问题转化为：在图G
中找一条哈密尔顿回路的问题.而A-B-D-F-G-E-C-A即是图中的一条哈密尔顿回路.照这个顺序安排座位就可以解决问题.
2.4匹配在数学竞赛中的应用
2.4.1匹配的概念和hall婚配定理
有个工厂，用六种颜色的纱生产双色布，每种颜色至少和其他三种颜色搭配.要求证明，一定可以找出三种不同的双色布，它们包含全部六种颜色.也就是说，按照所找到的三种不同双色布，每种颜色可以和另一种颜色配对，使得配对的对子不含相同颜色，这样就使每种颜色和跟它配成对子的颜色相匹配.用图论语言来说，就是要证明：如果6阶简单图G中每个顶点的度至少是3，则图G含有三条边，其中任意两条边都没有公共端点.设图G的三条边是e1，e2，e3，边ei的端点分别是u2i-1，u2i，i=1，2，3.则图G的6个顶点u1，u2，···，u6便按照e1，e2，e3配成对子：（u1，u2），（u3，u4），（u5，u6）.于是顶点u2i-1，u2i是匹配的，i=1，2，3.
一般的说，设G是n阶简单图，M是图G的某些边组成的集合.如果集合M中任意两条边都没有公共端点，则集合M叫做图G的一个边无关集.设u和v是图G的顶点.如果u和v是边无关集M的某条边的两个端点，则说顶点u和v在边无关集M下是匹配的.对于图G的一个匹配M，如果图G的每个顶点都在M下和另一个顶点匹配，则M叫做图G的完全匹配.如何判断一个简单图是否具有完美匹配，是匹配理论的中心问题之一.在匹配问题中，主要关心的是二部分图.具体地说，设图G是二部分图，X和Y是图G的顶点集合V的一个划分，
16