专题十六图论问题（一）四川师范大学数学与软件科学学院李昌勇一、基本知识1、完全图：每两个不同顶点均邻接的简单图.n阶完全图Kn的边数.2、定理1：设图G=（V，E），则G中所有顶点度之和等于边数的2倍，即EQ\I\SU(v∈V,,d(v))=2|E|.推论设图G=（V，E），则G中奇顶点的个数一定是偶数.☆定理2：二色中至少存在一个同色三角形.☆定理3：二色中没有同色三角形的充要条件是它可分解为一红一蓝的两条封闭折线，每条恰含有5条连线段.3、在处理图论问题中，经常考虑抽屉原理、极端原理，使用反证法、枚举法和数学归纳法等进行解决.二、典型问题分析1、10个人参加会议，会后统计出各人的朋友数为（ⅰ）3，3，3，3，5，6，6，6，6，6；（ⅱ）1，1，3，3，3，3，5，6，8，9.证明:两组统计数据都有误.2、设整数，试问：对哪样的，存在这样的图，它的个顶点的度数分别为？3、设是平面上的点集，其中任意两点之间的距离至少是1，证明：中至多有对点，每对点的距离恰好是1.4、某地区网球俱乐部的20名成员举行14场单打比赛，每人至少上场一次.证明：必有6场比赛，其中12个参赛者各不相同.5、证明：在任何六个人中，总可以找到三个相互认识的人或三个互相不认识的人.（认识是相互的）.6、某8个人参加一次集会．（1）如果其中任何5个人中都有3个人两两认识．求证：可以从中找出4个人两两认识；（2）试问，如果其中任何6个人中都有3人两两认识，那么是否一定可以找出4个人两两认识？7、设个新生中，任意3个人中有2个互相认识，任意4个人中有2个互不认识．试求的最大值．8、在二色完全图中，至少存在几个同色三角形.9、求最小正整数n，使得当以任意方式将的边染红、蓝二色时，总存在两个没有公共边的同色三角形.10、是否存在四个多项式，使得任意三个多项式的和有一个实根，而任意两个多项式的和没有实根？11、给定空间中的9个点，其中任何4点都不共面.在每一对点之间都连有一条线段，这些线段可染为红色或蓝色，也可不染色.试求出最小的n值，使得将其中任意n条线段中的每一条任意地染为红蓝二色之一，在这n条线段的集合中都必然包含有一个各边同色的三角形.12、一个具有10个顶点的图G，其中任何三顶点中至少有两点相连.试问G中至少有几条边？并且做出一个这样的图.练习题1、18个队进行比赛，在每一轮比赛中，每个队与另一个队比赛一场，并且在以后的各轮中这两个队不再比赛.现在比赛进入第9轮，证明在前8轮比赛中，一定有三个队，彼此之间尚未比赛过.2、国际乒乓球男女混合双打大奖赛有24对选手参加，赛前一些选手握了手，但同一对选手之间不握手.赛后某个男选手问每个选手的握手次数，各人的回答各不相同，问这名男选手的女搭档和多少人握了手？3、17名科学家中每一名和其余科学家通信，在他们的通信中仅讨论三个题目，而任两名科学家之间仅讨论一个题目.证明：其中至少有3名科学家，他们互相通信中讨论同一个题目.4、某俱乐部有名成员，对每一个人，其余的人中恰好有个愿与他打网球，个愿与他下象棋，个愿与他打乒乓.证明：俱乐部中有3个人，他们之间玩的游戏三种俱全.5、现有9个人，已知任意三人中总有两人相互认识，证明：必有四人相互之间都认识.6、一些数学家参加一次会议，其中每个数学家至多认识其中的三个数学家，而且如果两个数学家互不认识，则必存在一名数学家和他们都认识．试问参加了这次会议的数学家最多有多少个？7、求最小正整数，使在任何个无理数中，总有3个数，其中每两数之和仍为无理数.8、平面上有7个点，每三点的两两连线都组成一个非等边三角形．求证：一定可以找到4对三角形，使每对三角形的公共边既是其中一个三角形的最长边又是另一个三角形的最短边．9、给定平面上的点集，中任三点不共线，将中点任意分成83组，使每组至少有3个点，每点恰好属于一组.将每组中任两点均连成一线段，不在一组的两点不连成线段.这样得到一个图.显然不同连结线段的方式得到不同的图.图中所含以中的点为顶点的三角形的个数记为.（1）求的最小值；（2）设是使的一个图，若将的线段用4种颜色染色，每条线段恰好染一种颜色，则存在一种染色法，使中线段染色后，不含有同色三角形.专题十七图论问题（二）四川师范大学数学与软件科学学院李昌勇一、基本知识1、定义1：如果图的顶点集可以分为个两辆不交的非空子集，即，，，并且没有一条边，其两个端点都在上述同一子集内，称这样的图为部图．记作.2、定义2：如果在一个部图中，，任意两点都有和相邻，则称是完全部图，记作．3、设，记完全部图，这里，，令表示的边