2023年7月19日发(作者：)

第九章 图

9.1设V{u,v,w,x,y}，画出图G(V,E)，其中：

（1）E{(u,v),(u,x),(v,w),(v,y),(x,y)}

（2）E{(u,v),(v,w),(w,x),(w,y),(x,y)}

再求各个顶点的度数。

解

（1）见图9.1(a)。其中顶点u的度数是2，顶点v的度数是3，顶点x的度数是2，顶点y的度数是2，顶点w的度数是1。

u v

u v

y

y

(a)

x

w

x

(b)

w

图9.1 习题1图

（2）见图9.1(b)。其中顶点u的度数是1，顶点v的度数是2，顶点x的度数是2，顶点y的度数是2，顶点w的度数是3。

9.2 设G是具有4个顶点的完全图。

（1）画出图G。

（2）画出G的所有互不同构的生成子图？

解

（1）如图9.2(1)所示。

图9.2(1) 习题2图

（2） 如图9.6(2)所示

1 ﹒

﹒

﹒

﹒

﹒

﹒

﹒

﹒

图9.2(2) 习题2图

9.3 一个无向简单图，如果同构于它的补图，则称这个图为自互补图。

（1）试画出五个顶点的自互补图。

（2）证明一个自互补图一定只有4k或4k1个顶点（k为整数）。

解

（1）

1

G

v

G

v1

v2

v5

v2 v5

v3

(a)

v4 v3

(b)

图9.3 习题3图

v4

（2）因为n个顶点的无向完全图有11n(n1)条边，所以自互补图有n(n1)条边，24因此，n4k或4k1。

9.4 画出两个不同构的简单无向图。每一个图都仅有6个顶点，且每个顶点都均是3度，并指出这两个图为什么不同构。

解

图9.4 习题9.4图

9.5 证明任意两个同构的无向图，一定有一个同样的顶点度序列。顶点度序列是一组按大小排列的正整数。每一个数对应某一个顶点的度数。

证明

两个同构的无向图，度数相同的顶点数目一定相同，这样才能够建立起顶点之间的一一对2 应关系，进而建立起边的对应关系。所以，任意二个同构的无向图，一定有一个同样的顶点度序列。

9.6图9.6中所给的图(a)与图(b)是否同构？为什么？

(a)

图9.6 习题6图

(b)

解

左图9.2（a）中次数为4的点，与3个度数为1，一个度数为2的顶点相邻接，右图9.2（b）中度数为4的点，却与3个度数为1，一个度数为3的顶点相邻接。因此两图之间不存在同构映射，从而不同构。

9.7有207个人在一起欢聚。若已知每个人至少和5个人握了手，则至少有一个人不止和5个人握手。

证明

设v1,v2,...,v207代表这207个人，建立顶点集V{v1,v2,...,v207},对于其中的任意两个人vi,vj(ij)，若vi和vj握了手，则{vi,vj}E，得到边集E，则有一个无向图G(V，E)。若每一个人仅和其余5个人握过手，则d(vi)5，而此时图G的奇数度的顶点是207个，即是奇数个，产生矛盾。因此至少有一个人vi，d(vi)6。

9.8证明一个无向图的奇数度的顶点一定有偶数个。

证明

设G(V，E)是一个无向图。V1{vV|d(v)是奇数}，V2{vV|d(v)是偶数}，显然{V1,V2}是V的一个划分。所以d(v)d(v)d(v)，而d(v)是一个偶数，vVvV1vV2vV2所以vV1d(v)=d(v)－d(v)，其中d(v)2|E|也是一个偶数，偶数减去偶数仍然vVvV2vV是偶数，故vV1d(v)是偶数。

9.9 设

，分别是图G(V，E)中顶点的最小度数和最大度数。|V|n，|E|m，证明≤2m≤。

n证明

3 因为viVdevg)(2mi，对任意的viV，有devg，于是i)(ndeg(vi)n，即n2mn，所以vi2m。

n9.10证明由多于或等于2个人的人群，至少有二个人在这群人中朋友数相同。

证明

设v1,v2,...,vn代表这n(n2)个人，建立顶点集V{v1,v2,...,vn}，对于其中的任意两个人vi,vj(ij)，若vi和vj是朋友，则{vi,vj}E，得到边集E，则有一个无向图G(V，E)。由于每个顶点仅仅能够与另外的n1个顶点邻接，所以每个顶点的度数n1。因此，在G中顶点可能出现的度数是0，1，2，…,

n1。由于度数是0的顶点是孤立顶点，而度数为n1的顶点一定邻接其它n1个顶点的，所以在G中度数为0和度数为n1的顶点不可能同时出现。因此，在G中可以出现的顶点的度数应该分成以下两种情况：

(1) 0,1,2,„,

n2

(2) 1,2,3,„,

n1

上述两种情况最多有n1种不同的度数。根据鸽巢原理，至少有两个顶点具有相同的度数。故由多于或等于2个人的人群，至少有二个人在这群人中朋友数相同。

9.11

G(V，E)是一个简单无向图，若|E|证明

反证法。假设G不连通，不妨设G可分成两个不相连通的子图G1和G2，并假设它们中的顶点个数分别为n1和n2，当然|V|n1n2，因为ni1，所以(n11)(n21)0，从而有n1n2n1n210。

1(|V|1)(|V|2)，则G是连通图。

2|E|n1(n11)n2(n21)122(n1n2n1n2)

2221((n1n2)22n1n2(n1n2))

21(|V|23|V|22(n1n2)2n1n22))

21(|V|23|V|22(n1n2n1n21))

211(|V|23|V|2)(|V|1)(|V|2)

22这与假设相矛盾，因此G是连通的。

9.12

G(V，E)是一个简单图，试证明若G不连通，则G的补图G一定连通。

证明

4 若GV,E是不连通的，则G可分为n个连通分支G1(V1,E)，G2(V2,E2)，,Gn(Vn,En)。由于任意两个连通分支Gi,Gj(ij)之间不连通，因此两个顶点子集Vi与Vj之间的所有连线都在图G的补图G中。任取两个顶点u,v，则存在两种情况：

（a）u,v分别属于两个不同顶点子集Vi与Vj。由上可知，G包含边(u,v)，故u和v在G中是连通的。

（b）u,v属于同一个顶点子集Vi。可在另一个顶点子集Vj中取一个顶点w，由上可知，边(u,w)及边(v,w)均在G中，故邻接边(u,w)和(w,v)组成的路连接顶点u和v，即u和v在G中也是连通的。因此，当图G不连通时，G一定连通。

9.13已知关于人员a，b，c，d，e，f和g的下述事实：

(a) 说英语；

(b) 说英语和西班牙语；

(c) 说英语，意大利语和俄语；

(d) 说日语和西班牙语；

(e) 说德语和意大利语；

(f) 说法语，日语和俄语；

(g) 说法语和德语。

试问：上述七个人中是否任意两人都能交谈（如果必要，可由其余五人所组成的译员链帮忙），为什么？

解

以a，b，c，d，e，f和g为顶点，如能讲同一语言则作一边，得图9.7，图9.7是连通的，所以这7个人中，任意两个都能交谈。

b d

f

a

c

e

g

图9.7 习题13图

9.14（d1，d2，„dn）是一个非负整数的n元数组，若存在一个n个顶点的简单无向图，使得其顶点的度数分别是d1，d2，„dn，则称这个n元数组是可图的。证明

5 （1）(4，3，2，2，1)是可图的。

（2）（3，3，3，1）是不可图的。

（3）不失一般性设d1d2，dn证明：（d1，d2，„dn）是可图的当且仅当（d21,d31，„，dd11，dd111，dd12，…,dn）是可图的。

证明

（1）其构成图如图9.8所示。

图9.8 习题14(1)图

（2）（3，3，3，1）说明4阶无自回路的图中有3个顶点的度数为3，一个顶点的度数为1，而当有3个顶点的度数为3时，说明这3个顶点与其余各个顶点相邻接，这是，另一个顶点度数也应为3。与题设相矛盾，所以（3，3，3，1）是不可图的。

（3）先证明必要性。若 （d1，d2，„dn）是可图的，则（d21,d31，„，dd11，dd111，dd12，…,dn）是可图的。

设（d1，d2，„dn）构成图G的顶点为v1,v2,...,vn，且d(vi)di，可有以下两种情况：

(a)若v1关联的边正好是v1v2,v1v3,...,v1vd11,则去掉这些边所得之图，即为所要求的图。

(b)若v1关联的边中，有v1vj{v1v2,v1v3,...,v1vd11}，即jd11,令

j0max{j|v1vjE(G)}d11i0min{i|v1vjE(G)}d11

则有v1vj0E(G)，当jj0时，当ii0时，

v1vi0E(G)，v1viE(G)。v1vjE(G)；其线图如图9.9所示。考察与顶点vi0相邻接的di0个顶点，其中必有一个顶点vk与vj0不相邻接，否则就会产生dj0di01的矛盾。

6 v1

v1

vn

v2

vj0

vi0-1

vi0

vk

vd1+1

vn

v2

vj0

vi0-1 vi0 vk

vd1+

1v3

v3

图9.9 习题14(3)图 图9.10 习题14(3)图

作图G'G{v1vj0,vi0vk}{v1vi0,vkvj0},即得图9.10。于是G'仍是无向无自回路的线图，且有与G相同的度序列，只是G'的j0减少了，i0增大了。这个过程重复地做下去，总可得到与（a）相同的情况。因此，必要性得证。

再证充分性。若（d21,d31，„，dd11，dd111，dd12，…,dn）是可图的，则（d1，d2，„dn）也是可构成图的。

设前者所构成的图为G，顶点为v2,v3,,vn，且顶点的次数为d(vi)di1,2id11;d(vi)di,d11in时，G中增加一个新顶点v1，使v1与。因此，充分性得证。

v2,...,vd11相邻接，所得新图的顶点度序列为（d1，d2，„dn）9.15 一个简单连通的无向图的中心，定义为具有这样性质的一个顶点，即这个顶点到其余顶点之间的最大距离是最小的。（两点间的距离为两点间最少边的一条通路的边的数目）。

（1）举出仅有一个中心的图的例子。

（2）举出一个不止一个中心的图的例子。

（3）若T是一棵树，且T有两个中心，则这两个中心一定邻接。

解

（1）如图9.11(a)

（2）如图9.11(b)

（a） （b）

图9.11 习题15的图

（3）设顶点v的偏心数记为D(v)的中心。下面考察T的中心v。

7

maxd(v,u)。显然，具有最小偏心数的顶点v是GuV在树T(V,E)中，vV，不妨设D(v)d(v,v*)，则容易说明v一定是树叶。在树中删去全部树叶仍是一棵树，记为T1(V1,E1)，由于在T1中，vV1，D(1)(v)D(v)1，可见树T的中心仍在T1中。继续上述工作，直到只剩下一个顶点或剩下二个有一条边的相继顶点。这些顶点就是中心。

故若T是一棵树，且T有两个中心，则这两个中心一定邻接。

9.16

G是一个简单图，G(V，E)，G中顶点度数的最少值(G)|V|2，证明欲使此图不连通至少擦去(G)这么多顶点。（即点连通度k(G)=(G)）。

证明

因为G是简单图，所以每个顶点的度数最多为|V|1，现(G)|V|2，所以可以分两种情况讨论：

（a）若(G)|V|1，则GK|v|，因此k(G)|V|1(G)。

（b）若(G)|V|2，则必有两个顶点不相邻接，设v1,v2V，且v1与v2不相邻接。于是，对于任意的v3V,都有v1v3,v2v3E。因此，对于V中任意的|V|3个顶点的集合*V1,GV1一定是连通的，故必有k(G)|V|2(G)。大家知道对于任何一个图G都有k(G)(G)(G)（(G)是边连通度）。因此k(G)=(G)。

9.17

设G为n(n2)阶无向欧拉图，证明G中无桥。

证明

假设G中存在桥e(u,v)，由于G为欧拉图，所以e的两个端点在G中的度数均为偶数。因为e为G中桥， 所以G'Ge，由两个连通分支G1'和G2'组成。不妨设uV(G1'),vV(G2')，由于删除了e，因而在G1'和G2'中，dG1'(u),dG2'(v)为奇数度顶点，而对于任意的wV(G1')，wu，dG1'(w)为偶数，即G1'中只有一个奇度顶点u；类似地，G2'中也只有一个奇度顶点v。这与握手定理的推论矛盾，故G中不可能含桥。

9.18 一个连通的简单无向图，若每一个顶点的度数均是偶数，则此图不存在仅有一条边的割集。

证明

因为图中每一个顶点的度数均是偶数，所以该图为欧拉图，从而存在欧拉回路。又因为该8 图为简单无向图，则该欧拉回路至少有3条边。根据欧拉回路的性质知，删除图中任何一条边后，图仍然连通。因此，此图不存在仅有一条边的割集。

9.19

G(V,E)是一个图，

V是顶点集，

E是边集。若|V|n，则对于任意的vi,vjV(vivj)，vi到

vj有一条通路，一定有一条长度不超过n1的通路。

证明

对于任意的vi,vjV(vivj)，vi到

vj有一条通路，则由定理知，一定存在一条从vi到

vj的初等通路。因为图中只有n个顶点，故任意一条初等通路的长都不超过n1。因此，一定存在vi到

vj的长度不超过n1的初等通路。

9.20 证明在一个连通图中，任意两条最长路必有公共顶点。

证明

'''设G(V,E)是连通图，且有两条最长的简单路：l1:(v1,v2,...,vn)和l2:(v1,v2,...,vn)。假设l1和l2无公共点，取l1中一点v1，l2中一点v1'，由于G连通，必然有一条简单路'，得l3:(x1,x2,...,xk)，其中x1v1，xkv1'。设xj是l3中从左向右看第一个l2中的点vk一简单路l4:(x1,x2,...,xj)，设xi是l4中从右向左看第一个l1中的vg，则又得到一个简单路l5:(xi,xi1,...,xj),|l5|1，且l5中除了xi和xj外，没有l1，l2中的点，不妨设'''(v1,v2,...,xi)(xi,vg1,...,vn)，(v1',v2,...,xj)|(xj,xk1,...,vm)|，则可以取到简单路''l6:(v1,v2,...,xi,xi1,...,vk,...,v11)，因为|l5|1，所以l6min{|l1|,|l2|}，这样就可以得到一条更长的路，矛盾。因此，任意两条最长的简单路必有公共点。

9.21证明若一个连通简单无向图有且仅有两个顶点不是割点，（即除这2个不是割点顶点外，任何另外的一点若擦去图就不连通了），则此图是一条直线。

证明

设图G(V,E)，由于该图为连通简单无向图，则该图没有多重边。因此该图若有回路至少应有3个顶点。因为该连通简单无向图有且仅有两个顶点不是割点，所以该图没有回路。否则该图至少存在3个不是割点的顶点。一个没有回路的连通简单无向图至少存在两个1度顶点，设此两顶点为v1和v2，此两顶点不是割点。

假设该图不是一条直线，则图G中至少存在一个顶点vV，其度数d(v)3。因为图为连通且无回路，所以从顶点v出发至少存在3条通路，从v到v1的通路，从v到v2的通路和从。由此可见v3不是割点，也即图G存在3个不是割v到v3的通路（其中v3为该通路的终点）9 点的顶点v1,v2,v3，与已知矛盾。故该图是一条直线。

9.22 证明若一个无向图G没有孤立点，没有奇数度顶点，则它必包含有圈。

证明

如果图G有自环，则结论自然成立。

假设图G没有自环，由于图G没有孤立点，没有奇数度顶点，则每个顶点的度数至少是2。设L是图G中最长路中的一条，设其长度为m，这条路的一个端点设为a，考察G中与a关联的那些边，这些边中任何一条边的另一端必在L中，否则，将这个顶点加进L中就可得到一条更长的路。

如果G中每个顶点的度数至少为2，那么a也要关联于一条不在L上的边e。若e是环，则e本身就是回路。否则，e的另一个端点b在L上，而连通L中a到b的子路与边e就形成一个回路。如图9.12所示。

b

e

a

图9.12 习题22、23图

9.23

G(V，E)是一个简单连通图。若G中每个顶点的度数都大于1，则G中有圈。

证明

设L是图G中最长路中的一条，设其长度为m，这条路的一个端点设为a，考察G中与a关联的那些边，这些边中任何一条边的另一端必在L中，否则，将这个顶点加进L中就可得到一条更长的路。

因为G中每个顶点的度数都大于1，则G中每个顶点的度数至少为2，那么a也要关联于一条不在L上的边e。e的另一个端点b在L上，而连通L中a到b的子路与边e就形成一个回路。如图9.12所示。

9.24

G(V,E)是一个简单无向图。若G是一个二部图（偶图），且每一个顶点的度数都是3度，{V1,V2}是G作为二部图顶点集一个划分。证明|V1||V2|。

证明

因为每一个顶点的度数都是3度，所以由二分图的定义知，图共有3|V1|条边，每条边对应2个度数，故图的总度数为6|V1|。由握手定理知，3|V1|3|V2|6|V1|，从而有|V1||V2|。

9.25

G(V,E)是简单图，证明以下三条等价：

10 （1）G是一个顶点2着色的图；

（2）G是一个二部图（偶图）；

（3）G是所有回路都是由偶数条边组成。

证明

（1）（2）：

G能够顶点2着色，则把顶点划分成两个分类V1和V2，其中V1、V2分别是着色相同的顶点，则{V1,V2}就作为二部图顶点集的一个划分。因此，G是一个二部图。

（2）（3）：如果G是二部图，{V1,V2}是它的二分类。令(vio,vi1,,vik,vi0)是G中的一条长度为k1的回路。不失一般性，设vi0V1，则由二部图的定义知，vi2,vi4,,vi0V1，vi1,Vi3,vikV2。因此，k是奇数，从而k1是偶数。

故G是所有回路都是由偶数条边组成。

（3）（1）：

先假设G是连通的，取定v0V，定义V的二个子集如下：

V1{vi|vi到v0的距离是偶数}，V2{vi|vi到v0的距离是奇数}

任取e{vi,vj)E，若vi,vjV1，由V1的定义知，从vi到v0有一条初等通路，其长为偶数，从vj到v0也有一条长为偶数的初等通路，再加上边e得到一条回路，此回路的长度是偶数+偶数+1，即为奇数，与题设矛盾。矛盾说明vi与vj不可能同时属于V1。同样可以证明vi与vj不可能同时属于V2，即{V1,V2}是G的一个二分类。这样图G中每一条边，它所关联的两个顶点一个在V1 中，一个在V2中，将V1中所有顶点着上c1色，V2中所有顶点着上c2色，就得到图G的一种正常着色。

故G是一个顶点2着色的图。

如果图G不是连通的，则可以对G的诸连通分支的顶点2着色，从而得到对图G的顶点2着色。

9.26已知：a，b，c，d，e，f，g的下述事实：

(a)说汉语、日语；

(b)说日语、法语；

(c)说德语、法语、西班牙语；

(d)说汉语、德语、俄语、葡萄牙语；

(e)说俄语、朝语；

(f)说朝语、西班牙语；

(g)说葡萄牙语。

11 试问：能否将七个人分成二组，使同一组中没有二个人能互相交谈？并用图论方法，说明你的结论。

解

把每个人对应成相应的顶点，两个能够交谈当且仅当相应的顶点相邻，得图9.13显然该图是一个二部图。因此能将七个人分成二组{a,c,e,g}和{b,d,f}，使同一组中没有二个人能互相交谈。

图9.13 习题26图

9.27图9.14中哪个图是欧拉图？哪个图是哈密尔顿图？哪个图有欧拉通路？哪个图有哈密尔顿通路？

(a) (b)

(c)

图9.14 习题27图

(d)

解

图9.14（a）中有两个奇数度顶点，如图中“黑点”所示。其余的全是偶数度顶点，根据定理，该图存在欧拉通路，但不存在欧拉回路，因此该图不是欧拉图。该图同样存在哈密尔顿通路，沿着边走就可。但是不存在哈密尔顿回路，因此不是哈密尔顿图。

图9.14（b）中有六个奇数度顶点，因此它不存在欧拉通路，也不是欧拉图。

图9.14（c）中两个奇数度顶点，如图中“黑点”所示。其余的全是偶数度顶点，根据定理，该图存在欧拉通路，但不存在欧拉回路，因此该图不是欧拉图。该图存在哈密尔顿通路，不是哈密尔顿图。

图9.18（d）中全都是奇数度的顶点，因此不是欧拉图。图中存在哈密尔顿回路，因此12 是哈密尔顿图。

9.28当 n是什么数时，完全图kn是欧拉图？请说明理由。

证明

kn有n个顶点，每个顶点的度数为n1，故当n(3)为奇数时，图kn有一条欧拉回路。9.29 （1）画一个欧拉图，但不是哈密尔顿图。

（2）画一个哈密尔顿图，但不是欧拉图。

（3）画一个有哈密尔顿路的非哈密尔顿图

（4）画一个有哈密尔顿通路但无哈密尔顿图的欧拉图。

解

（1）如图9.15（a）所示。

（2）如图9.15（b）所示。

（3）如图9.15（c）所示。

（4）如图9.15（d）所示。

（a）

（b）

图9.15 习题29图

（c）

（d）

9.30 一个连通图中有一个顶点，称为桥。若擦去这个顶点后，图就不连通了，请画一个欧拉图，但不是哈密尔顿图且没有桥。

解：如图9.16所示

图9.16 习题30图 图9.17 习题31图

9.31画一个有7个顶点的简单无向图，满足

（1）它有哈密尔顿通路。

（2）它不是哈密尔顿图。

（3）它不是欧拉图。

（4）它能一笔画。

解

如图9.17。

9.32 证明一个无向图若有2m个奇数顶点，则此图至少要m笔才能画，且能用m笔画。

证明

根据欧拉通路的性质可知，在图中存在一个奇数度顶点到另一个奇数度顶点欧拉通路，该通路可以一笔画出，且在画图过程中其余经过的顶点均为偶数度，删除通路中的边，所得图中13 有2(m1)个奇数度顶点。重复上述过程m次后，图中没有任何边。因此此图至少要m笔才能画，且能用m笔画。

9.33 如果可能，请画一个顶点是偶数，边是奇数的欧拉图。否则说明理由。

解

图9.18 习题33图

9.34 画一个欧拉图，它是简单无向图，有偶数条边，但有奇数个顶点。

图9.19 习题34图

9.35 证明一个欧拉图不存在割边，即不存在一条边，拿去此边后，原图变成不连通的两部分。

证明

因为图G是欧拉图，所以G存在一条经过每条边一次且仅一次的回路，删除G中的任何一条边，图仍然连通，故一个欧拉图不存在割边。

9.36

G(V，E)是一个简单连通图。且G是一个二部图（偶图），相应地顶点分类为{V1,V2}，且|V1||V2|。证明G不是哈密尔顿图。

证明

因为|V1||V2|，不妨设|V1||V2|，从图中去掉V1中的顶点后, 得到|V2|个连通分枝。因为所得到的连通分枝数目|V2|大于所去掉的顶点数目|V1|，即W(GV1)|V2||V1|，所以由哈密尔顿图的必要条件知，G不是哈密尔顿图。

9.37如果一个无向图中每一条边给它定一个方向，使所得有向图是强连通的，那么称这个图为可定向的。证明任何一个哈密尔顿图是可定向的。

证明

设G是哈密尔顿图，则在图中一定存在一条经过所有顶点一次且仅一次的回路C，对C上的每一条边沿回路按顺时针方向加上方向，不在回路上的边任意加方向所得之图是一个有向图，该有向图中存在一条经过G中每个顶点一次且仅一次的回路，所以此有向图是强连通的。因此，任何一个哈密尔顿图是可定向的。

9.38

G(V,E)是一个简单连通图。eE是G中一条边，若从图G中擦去边e，则G不连通，说e是G中的桥。证明若G是哈密尔顿图，则G中没有一条边是桥。

证明

因为G是哈密尔顿图，所以一定存在哈密尔顿圈，它包括图G中的任意一个顶点，删去14 其中的任意一条边，若删除的不是圈中的边，则哈密尔顿圈仍然存在，图仍然连通；若删除的是圈中的边，则图中存在一条哈密尔顿路，图仍然连通。

因此G中无任何一条边是桥。

9.39

G(V，E)是一个简单连通图。vE是G中一个顶点，若从图G中擦去顶点v，其余不动，则G不连通，说v是G中的桥。证明若G是哈密尔顿图，则G中没有一个顶点是桥。

证明

因为G是哈密尔顿图，所以一定存在哈密尔顿圈，它包括图G中的任意一个顶点，删去其中的任意一个顶点，则图中存在一条哈密尔顿路，图仍然连通。因此G中无任何一个顶点是桥。

9.40 有12个人围坐一圆桌，边会餐边交流乒乓球技术。已知这12个人中，每个人至少和其余的6人打过球，试问是否有一种坐法，使每个人左、右俩人都和他打过球？请说明原因。

证明

设GV,E是一个有12个顶点的简单无向图，每一个顶点表示一个人，两个顶点之间有一条边当且仅当对应的人打过球。因为每个人至少和其余的6人打过球，所以任意一个顶点的度数都6，因此对于任意两个顶点u,v，deg(u)deg(v)12，即满足充分性条件，故图存在一个哈密尔顿圈，沿哈密尔顿圈就坐，就能使每个人左、右俩人都和他打过球。

9.41 有12个人，围坐一个圆桌的四周开会。已知这12个人中的任意的二个人能认识其余的10个人，则这12个人围坐一圈能使每一个人都认识各自的左、右邻人。

解

设GV,E是一个有12个顶点的简单无向图，每一个顶点表示一个人，两个顶点相邻当且仅当两个人认识。因为这12个人中的任意的二个人能认识其余的10个人。则对于任意两顶点u和v，其与其余10个顶点的度数之和d10(u)d10(v)10。

若u和v相邻，则d(u)d(v)d10(u)1d10(v)112。

若u和v不相邻，则V{u,v}中恰有10个顶点。如果d10(u)d10(v)10，且其余10个顶点必与u或v相邻接，则至少有一个顶点只能与u和v 中的一个顶点相邻（否则，2102010，矛盾）。设w与u相邻，

w与v不相邻。此时，对于顶点u,w来说，都不与v相邻，即u,w合起来不能认识v，故不能认识所留下的10个人，这与假设相矛盾。故d(u)d(v)d10(u)d10(v)11。如果d10(u)d10(v)11，且其余10个顶点必与u或v相邻接，则至少有一个顶点只能与u和v 中的一个顶点相邻（否则210=2011，矛盾）。设w与u相邻，

w与v不相邻。此时，对于顶点u,w来说，都不与v相邻，即u,w合起来不能认识v，故不能认识所留下的10个人，这与假设矛盾。故d(u)d(v)d10(u)d10(v)12，由哈密尔顿的充分条件知，图中存在一条哈密尔顿圈，因此，这12个人沿哈密尔顿圈就坐，能使每一个人都认识各自的左、右的邻人。

15 9.42

G(V,E)是一个连通无向图。我们做一个新图G(V,E)，使

V{v|vV}，''在新图G中，

{v1,v2}E，当且仅当在原图G中有一条从v1到v2的哈密尔顿通路。一个图G叫自哈密尔顿路图，若G与G同构。请画出两个不同构的自哈密尔顿路图，他们都各有4个顶点。

解

图9.20 习题42图

9.43 画两个最简单的不同构的非平面图

解

图9.21（a）是具有6个顶点的K3,3，它是非平面图。

图9.21（b）也具有5个顶点的k5，它是非平面图。显然两个图不同构。

(a)

(b)

图9.21 习题42图

9.44 画二个六个顶点的图，它们都是非平面图，但互不同构。

解

e13，图9.22（a）是具有6个顶点的K3,3,它是非平面图。图9.22（b）也具有6个顶点，每个区域至少由3条边围成，1336612，因此它不是平面图。而且图（a）每个顶点的度数都是3，图（b）两个顶点的度数是5，其余的顶点度数均为4，因此这两个图不同构。

(a) (b)

16 图9.22 习题43图

9.45试画一个有8个顶点的简单连通图，让它和它的补图都是平面图。

解

图9.23 习题45图

9.46

G(V,E)是一个无向图。若|V|11，则G或者G的补图G是非平面图。

证明

设G和G都是平面图，设图G的顶点数为v，边数为e，图G的顶点数为v'，边数为e'，显然vv'，ee'1v(v1)。由不等式e3v6,e'3v'63v6，相加得21v(v1)ee'6v12，从而有v213v24(v2)(v11)20，显然应有2|V|11。与假设矛盾。故G或者G的补图G是非平面图。

9.47 证明小于30条边的简单平面图至少有一个顶点的度数小于或等于4。

证明

假设每个顶点的度数>4,即deg(vi)5，设图G的顶点数为v，边数为e。因为2edeg(vi)5v，即vi1v26e。由于e3v6，代入后得到ee6，即有e30，55K(v2)。这是e，v分别是G的K2与边数小于30相矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于或等于4。

9.48 设G是每一个面至少由K(K3)条边围成，则e边数和顶点数。

证明

设图G的顶点数为v，边数为e，平面数为r。因为每一个面至少由K(K3)条边围成。所以2eKr，即r2e2eK(v2)2，即e，而ver2，故ve。

KKK29.49 证明具有6个顶点12条边的连通平面简单图，它的每一个面都是由3条边组成。

证明

设图G的顶点数为v，边数为e，平面数为r。由题意知，v6,e12，由欧拉公式17 r2ev8，设至少有一个区域由4条边围成，则有2e3r24，从而有e12。与e12矛盾。故每一个面都是由3条边组成。

9.50一个连通的简单平面图有8个顶点18条边。此图嵌入平面后，会把平面分成几个小区域？

解

设图G的顶点数为v，边数为e，平面数为r，则题意知，v8,e18，由欧拉公式r2ev12，因此，此图嵌入平面后，会把平面分成12个小区域。

18