7.图
1.设G有16条边，有三个四度顶点，四个三度顶点，其余顶点的度数都小于3，问G中至少
有几个顶点？
答：总度数=16*2=32
3*4+4*3=24
（32-24）/2=4 至少有 3+4+4=11
至少有11个顶点
2．设9阶无向图G中，每个顶点的度数不是5就是6，证明G中至少有5个六度定点或者至少
有6个5度顶点
证明，因为： 4*6+5*5=24+25=49不可能，
所以当n6<4 时， n5>=6 满足条件
当 n6>=5时，满足条件
得证
3.空间不可能存在奇数个面而且每个面均有奇数条棱的多面体
答： 假如有 奇数个面 n 每个面都有奇数个棱mi(I=1,2,…n)，
那么 m1+m2+…+mn= D mi为奇数，n奇数，所以D为奇数
但对于上式来说，每条棱都记了两次，那么 D=2*(总棱数) 为偶数 矛盾
所以空间不可能存在奇数个面而且每个面均有奇数条棱的多面体
4.在一次象旗比赛中，任意两个选手之间至多只下一盘棋，又每个人至少下一盘，证明总
能找到两名选手，他们下过的盘数是相同的
证明：建一个图的模型：每个选手相当于图的顶点，选手下的盘数相当于顶点得度数，两
个选手的对局相当于两个顶点的边，已知 顶点的度数是 1----n-1, 选手有n个，根据鸽
巢原理
可知，比存在两个顶点的度数相同，也就是总能找到两名选手，他们下过的盘数是相同的
。
5.设n阶无向简单图G为3次图(3-正则图)，边数m和n满足以下关系2n-3=m
问G有几种非同构的情况？并证明你的结论
解：3n=2m 2n-3=m => n=6 m=9
所以G是6阶 3正则图.设G1，G2均为无向简单图，G1同构于 G2 等价于 G1的补图同构
于G2的补图。所以可知 有两种同构的情况
6．下面给出的两个整数列，哪个是可图化的，对于可图化的请至少给出三个非同构的图
1） d=(1,2,2,4,4,5) 可图化
2） d=(1,1,2,2,3,3,5) 不可图化
非同构的图，赫赫在BBS上没法画！
7.判断下列三个整数列中哪些是可以简单图化的？对于可简单图化的试给出两个非同构的
图.
1)(6,6,5,5,3,3,2)
(6,6,5,5,3,3,2)<=>(5,4,4,2,2,1)<=><3,3,1,1,0)<=>,<2,0,0,0> 显然不可以简单图化
2）（5，3，3，2，2，1）<=>(2,2,1,1,0)<=>(1,0,1,0) 显然可以简单图化(赫赫，图在
BBS没法画)
3）（3，3，2，2，2，2）<=>(2,1,1,2,2)（不符合定理的条件,可先调整顶点次序）
<=>(2,2,2,1,1)(根据课本例题）
<=>(1,1,1,1)显然（1，1，1，1）是可简单图化的
8.9题（略）大家一定要画呀，挺好的一道题呀！！！
10,现有5个4阶的无向简单图，他们均有3条边，证明这5个图中至少有两个是同构的
证明:可以得知，这样的非同构的图有3个，所以得证
(图省略)
11.设G为n阶自补图，证明 n=4k或者n=4k+1其中 k为正整数。
证明 设n阶自补
图中边数为 m, 所以度数为 2m
显然n(n-1)=2*2m=4m =>n=4k,或者n=4k+1
12.设G是6阶简单无向图，证明G或者G的补图存在3个顶点彼此相邻
证明;通过着色问题可以解决，
是G图的边着红色，是G补图的边着蓝色
那么从一个顶点出来的边至少有3条边是同色的，不妨设为红色
那么对于这三条边的另的三个顶点之间，如果有一条是红色的，得证
否则都是蓝色的，得证，
13.若无向图G中恰有两个奇数顶点，证明这两个奇数顶点必然相通
证明：解题思路：反证法，如果不相通，那么这两个奇数顶点位于不同的连通分支中
，那么存在某连通分支有且只有一个奇数顶点，与可图化的定理矛盾
得证
14.设n(n≥3)阶无向简单图G是连通的，但不是完全图，证明存在u,v,w∈V(G),使得
(u,v),(v,w) ∈E(G),而(u,w) 不属于E(G)
证明：因为G连通图，所以必存在一个经过所有顶点得连通路
设为 u1 , u2, … un
如果对于任意(u,v),(v,w) ∈E(G),而(u,w) ∈E(G)
那么
得出G为完全图，矛盾，所以得证
15.设G是无向简单图,δ(G) ≥2,证明G中存在长度大于等于δ(G)+1的圈
证明： 用极大路径法证明，易
16.设G是无向简单图，δ(G)≥3 证明G中各圈长度的最大公约数为1或者2。
证明：用极大路径法构造一个长度为m的一个圈 d1,d2,….dm
因为δ(G)≥3,所以 dj(1
w) 连接，那么就能构成了两个圈n1,n2,而且 |n1|+|n2|=m+2
如果各圈长度存在最大公约数Q≥3，那么|n1|+|n2|和m也有最大公约数Q，这与|n1|+|n2
|=m+2矛盾，所以G中各圈长度的最大公约数为1或者2
(谢谢riveria同学！！！！！！！！！！！！！)
17.设G为n阶无向简单图，δ(G) ≥n-2 证明k(G)= δ(G)
证明 因为 δ(G) ≤n-1，所以δ(G)只有两种取值可能
1)当δ(G)=n-1,那么G为完全图，所以G的点连通度为n-1,得k(G)= δ(G)
2) δ(G)=n-2,
=>当去掉任意 n-3个点时，剩下的三个顶点 dn1,dn2,dn3≥1 , 那么d1,dn2,dn3 构成的
图至少存在2条边，且G为n阶无向图，所以 任去掉n-3个点，d1,dn2,dn3仍然是连通的。
=>当去掉任意 n-r(n>r>3)个点，身下 r个顶点 ,dn1,dn2,…dnr≥r-2,至少存在 一个r-
1的通路，那么剩下的一个点也与这个通路上的点有边，所以是连通的
选取没有边的两个顶点dn1,dn2(因为δ(G)=n-2,所以必存在没有边相联的两个顶点)，去
掉剩余的得n-2个顶点，dn1和dn2构成了两个连通分支。
综上所述， k(G)=n-2=δ(G)
18.设G是n阶无向简单图，证明
1)当δ(G) ≥n/2时，G为连通
图；2)当δ(G) ≥1/2(n+k-1)时，G为k-连通图
证明， 要用到n阶简单图的最大度≤n-1
用反证法，假设G至少有两个连通分支，设G1,G2为其中的两个，并设G1,G2的阶数分别为
n1,和n2,则n1+n2≤n,且min{n1,n2}≤n/2(或者n/2-1)。于是，对于任意的v∈V(G1)
d(V) ≤n/2-1
2) 利用1的结果，要证明G是k阶连通图，只需证明从G中删除任意(k-1)各所得图依然连通
，设V’为V(G)的任意子集且|V’|=k-1,令G’=G-V’，则G’为n-n-k+1=n’阶无向简单图
，而
δ(G’) ≥δ(G) –(k-1) ≥1/2(n+k-1)-(k-1)=1/2(n-k+1)=1/2n’ 可知G’连通，故G
’为k连通图
19.设G是围长为4的k-正则图
1） 证明 G中至少有2k个顶点
2） 当 G中正好有2k顶点时，证明在同构的意义下G是唯一的。
证明：(1)显然k>=2，否则围长不可能为4(不可能有圈)。
对于G中任一个围长为4的圈，其中每个顶点除圈中的点外，至少还连接k-2个点，(不可能
在与圈中的点连接，否则存在比围长小的圈)
取该圈中2个相邻的顶点v1,v2，显然v1所连接的k-2个点和v2所连接的k-2个点没有交集
(否则围长为3)，此时G至少有(k-2) + (k-2) + 4个顶点，即G至少有2k个顶点。
2)假设有2个图G1和G2，它们都是围长为4的K-正则图，且正好有2k个顶点。
将G1上一个围长为4的圈的顶点依次标记为v1_1, v1_2, v1_3, v1_4。
19.2.1 如果没有顶点了，此时G1是个正方形，G2也是个正方形，G1≌G2。
19.2.2 如果还有顶点，显然v1_1和v1_3连接的k-2个点是完全一样的，v1_2和v1_4连接
的k-2
个点也是完全一样的(否则G1不止有2k个顶点)。
在与v1_1和v1_3连接的k-2个点中任取一点v，显然v不能与v1_2或v1_4相连，否则根据
19.(1)，围长为3；v也不能与与v1_1和v1_3连接的k-2个点中除v外任意一点相连，否则
围长为3。
v的度数为k，除与v1_1和v1_3连接外，只能与所有与v1_2和v1_4连接的k-2个点相连。
即与v1_1和v1_3连接的k-2个点中任意一点都与所有与v1_2和v1_4连接的k-2个点相连，
与v1_2和v1_4连接的k-2个点中任意一点也都与所有与v1_1和v1_3连接的k-2个点相连。
这样就得到G1中所有的边了。
将与v1_1和v1_3连接的k-2个点任意标记为 v1_5, ..., v1_k+2，将与v1_2和v1_4连接
的k-2个点任意标记为 v1_k+3, ..., v1_2k。
用同样的方法，将G2上的顶点分别标记为v2_1, v2_2, ..., v2_2k。
做映射f(v1_i)=v2_i，显然对于任意(v1_i, v1_j)∈E(G1)，都有
(f(v1_i), f(v1_j))=(v2_i, v2_j)∈E(G2)。根据定义，G1和G2是同构的。
综合19.2.1和19.2.2，G1和G2同构，即在同构的意义下G是唯一的。
20.设G是n阶无向简单图，其直径为d(G)=2, ο(G)=n-2，证明G的边数m≥2n-4
证明：取其中度数为n-2 的顶点 dm 那么 它与顶点 d1,d2,
…. dn-2,存在 n-2条边，
对于顶点d1,d2, …. dn-2来说，每个顶点上必须再加上一条边才能保证 d(G)=2,否则d(
G) ≠2
得证
21,设n阶无向图G中有m 条边，已知m≥n,证明G中必含圈
证明：假如δ(G) ≥2 ，显然得证
如果存在 d(G)=1，0，那么去掉改顶点 ，那么m-m’ ≥n-n’,直到保证δ(G) ≥2,
当m-m’=3≥n-n’ 时 显然该图有圈。（有点象归纳法）
22.设n(n≥2)阶无向简单连通图G中不含有偶圈，证明G中的块或为K2或为奇圈
证明：分类讨论
1.G中不含奇圈，因为题设给出G中不含偶圈，所以G中不含圈，所以任意条边都是桥,也就
是
任意个点都是割点，所以G中的块为K2,
2.G中含有奇圈，讨论奇圈中的相对位置。
可以证明两奇圈如果有边重合的话 必可以从中找到一个偶圈，方法如下：
若重合的边是一段连续的边，那么两奇圈剩余的边可以构成一偶圈
若G1,G2重合的边是不连续的，G1被划分为若干段，设其中一段L1=a1e1a2e2...am为其中
一段 若L1为奇数阶 则可和(a1, am)构成偶圈 否则L1(偶数) ∪ {G2-(a1, am)(偶数)}构
成偶圈
23,这个图很容易画出来！！
24.将无向完全图Kn的边涂上红色或者蓝色，
1， 证明对于n≥6,任何一种随意的涂法，总存在红色的K3或蓝色的K3
证明：这道题和图的第12题类似
2．用1）的结论证明任何6个人中，或者有3个人彼此认识，或有3个人彼此不认识
证明：把本题转化为图的模型，然后利用第一题的结论即可
把6个人看作是6个顶点，两个人认识就着红边，两个人不认识就着蓝边，
所以存在红色的K3或者蓝色的K3，也就是或者有3个人彼此认识，或有3个人彼此不
认识
3．证明对于n≥7,如果有6条边或者更多条红色的边关联与1个顶点，则在Kn中存在红色的
K4或者存在蓝色轭K3
证明：利用1的结论，可知，顶点d1有6条红边，这6条红边所关联的六个顶点构成的图中
总存在红色的K3或蓝色的K3，当存在红色的K3时，和顶点d1一起构成红色K4，得证；存在
蓝色K3时，得证
25,设D为竞赛图，对于任意u,v,w∈V(D),若
D为传递的竞赛图，证明n阶传递的竞赛图不是强连通的。
证明：反证法
如果存在 u u1 u2 u3,….,v 通过
同样如果是强连通的，那么存在 v v1,v2,v3,…,u,通过
D)
这与D是竞赛图矛盾。