第19讲
图论初步

1．某会议有n(n≥4)名代表出席，已知任意4名代表中都有1人与其余3人相识。求证：任意4名代表中必有1人与其余n-1名代表都相识。

2．设n是一个正整数，有n名学生参加数学竞赛，其中某些学生是相识的。已知对任意k(k是给定的整数，2≤k≤n-1)名学生，他们都恰有一个公共的熟人。

证明：k=2或k=n-1。

3．设G是连通的简单图，所有顶点构成的集合为V，所有边构成的集合为E。称E的子集H为G的“偶度子图”，如果对任何x∈V,H中一共有偶数条边以x为顶点。设|V|=v,|E|=e。请问G一共有多少个偶度子图？注意，E的空子集∅也被视为一个偶度子图。

4．给定正整数n≥6，求最小的m，使得在任意n个点m条边的简单图中，必然存在两个无公共顶点的圈。

5．设n≥4是整数。有n名乒乓球选手参加一次单打比赛，每两名选手之间恰好比赛一场，且比赛无平局。设w _i 和l _i 分别为第i名选手的胜利次数和失败次数。试证明：若 (w _i -l _i ) ³ <0，则一定存在4名选手，在这4人之间的比赛中，其中一人输掉了所有比赛，另外3人各胜了两场比赛。

6．一个有向图中没有有向圈，且任意一条有向路的长度不超过99。试证明：可以将所有边二染色，使得任意一条单色有向路的长度不超过9。

7．给定整数n≥4，求满足下列条件的最小整数m：对{0,1,…,2 ⁿ -1}的任意一个m元子集A，都可以找到两两不同的a ₁ ,a ₂ ,…,a _n ∈A，使得若对每个i，记a _i 在二进制下从右至左数的第i位为x _i ，则x ₁ =x ₂ =…=x _n 。

8．设a,b是给定的正整数。现有一些砝码，已知这些砝码可以分成等重的a堆，也可以分成等重的b堆，求砝码个数的最小可能值。