§0 (综述)
§1 (图的基本概念与应用)
(本页)
§2
(特殊图)
§3 (染色问题)
§4 (竞赛中的问题)
§1 图的基本概念与应用
图是一个有序三元组 
．在实际问题中，
代表对象集合，关联函数 
及边集
反映了对象集合的一种二元关联关系，这正是图的最本质的内容．在现实生活中，我们对所考察的对象经常关心的也正是这样一种二元关系．例如，在人的集合中，两个人或是互相认识，或是互相不认识，因此，“认识”
就是人的集合中的二元关系；地图上各个国家组成的集合中，“相邻”（有公共边界）也是一个二元关系；运输问题中，车站之间有无直通道路连结，又反映了车站集合的一个二元关系；政府各部门是相互独立，还是彼此制约，反映了它们之间的二元关系，等等．总之，一个系统或结构，如果具有二元关系，换句话说，凡是能用点线连接的图形表示的问题，便可以考虑用图作为它的数学模型，使用图论的概念、理论和方法进行研究．二元关系比比皆是，这就决定了图论的应用有极其广阔的前景．
例 1 证明：在任何一群人中，认识这一群人中奇数个人的人有偶数个．（匈牙利奥林匹克数学竞赛题）
证 把每个人作为图的一个顶点，如果两个人互相认识则在相应顶点间连上一条边．这样人与人的认识关系就构成了一个图．图中每个顶点的度数就是该顶点所代表的人认识的人数．这样本题论断就是第一章推论 4 的一个直观的表现．其结论是显然的．
把推论 4 改换成其它的叙述形式，又可构造出以下问题：
试证：在所有生活在地球上的人们中，和奇数个人握过手的人有偶数个；
试证：在任何一个多面体中，有奇数条棱围成的面有偶数个；
试证：在任何一个多面体中，有奇数条棱交汇成的顶点有偶数个．
例 2 如果认识关系是相互的，证明在任何一群人中，至少有两个人在这群人中认识的人数相同．
证 设这群人有 
个．类似例 1，得到 
阶图 
．设 
是 
的任一顶点，它的度可能是 
．但是注意到，如果 
有一个顶点，它的度为 0（这个人谁也不认识，那么图 
中就不会有度为 
的顶点（这群人中就不会有认识所有其它人的人．同理，如果有一个顶点度为 
，中就不会有度为 0 的顶点．于是 
的 
个顶点的度在 
或 
中取值．无论哪种情况，
个顶点的度只有 
个可能取的值．按照组合数学中著名的抽屉原则，至少有两个顶点的度相同，这就是说，至少有两个人认识的人数相同．
例 3 某次会议有 
名代表出席，已知任意的四名代表中都有一人与其余的三个人握过手，证明任意四名代表中必有一人与其余的
名代表都握过手．
证明 (证一，见相关知识 注1；证二如下)
证二 用 
个顶点表示 
名代表．如果两名代表没有握过手，则在相应顶点间连上一条边，这样也可以得到一个简单图
．问题转化为：
的任意四个顶点中都有一个顶点与其余三个顶点不邻接，要证明的结论是在 
的任意四个顶点中，必有一个顶点与其余的 
个顶点都不邻接．
首先，图 
中不会出现如图 3 中（Ⅰ）和（Ⅱ）的情况，否则与已知矛盾．
（Ⅰ） （Ⅱ）
图 3
其次，若图 
中无边，或仅有一条边结论显然成立．若 
有两条边 
，
，则 
，
必定邻接（否则出现（Ⅰ）），除 
，
的三个端点外，在 
的其余 
个顶点中，没有任何一个点能与其余顶点邻接．否则，不外图 4 的（1），（2），（3）三种情况．而导致出现（Ⅰ），（3）导致出现（Ⅱ），都引起矛盾．
图 4
因此，
的任何四个顶点中，必有一个顶点与 
其余的 
个顶点都不邻接．