图论第二章和第四章的课后习题

图论第二章和第四章书后练习题

2.2 给出满足下列条件的图或说明这样的图为什么不存在

(a)没有奇点的图。

(b)所有顶点的度为三的图。

(c)阶至少为5的图G,且对于G中任意两个邻接的顶点u,v,均有degu?degv。

(d)阶至少为5的非完全图H,且对于H中任意两个不邻接的顶点u,v,均有degu?degv。 解：（a）

（b）

(c)

(d)

2.4 给出一个阶为6且边数为10的图G,满足?(G)?3,?(G)?4. 解：所求图如下所示：

2.6 在一个阶为3n(n?1)的图中，若度为n?1,n和n?1的顶点数个数均为n，则n必为偶数。

证：∵n-1+n+n+1=3n;

∴图中仅有度为n+1,n,n-1三种度的顶点 ∑deg(v)=(n-1)n+n*n+(n+1)n=3n2 由图论第一定理知，3n为偶数 则n为偶数。

2.8 设G为n阶图，若对G中任意三个互不邻接的顶点u,v和w，都有

degu?degv?degw?n?1,则G一定是连通的吗？

2

解：不一定，如下图：

2.10 我们已经知道，若n阶图G的任意两个不邻接的顶点u和v都满足

degu?degv?n?2,则G可能不连通。

(a) 证明：存在n阶的连通图G，它满足：对G中两个任意不邻接的顶点u和v，都有degu?degv?n?2,且G有两个不邻接的顶点x和y，使得degx?degy=n?2。 (b) 证明：若n阶图G的任意两个不邻接的顶点u和v都满足degu?degv?n?2,则G至多有两个连通分支。 (c) (b)中的界是紧的吗？

（a）证：假设degu?degv?n?1，则由定理4可知G不是联通的，这与已知矛盾。 ∴原结论正确。

（b）证：假设存在G1，G2,G3 三个连通分支，其阶数分别为n1,n2,n3,且n1+n2+n3≤n;

取u∈G1 v∈G2

dG(u)?dG(v)?dG1(U)?dG2(v)?n1?1?n2?1?n?n3?2?n?3 矛盾！

∴至多有两个连通分支 (c)是的

2.12证明：若n阶图G满足?(G)??(G)?n?1，则G是连通的，且diam(G)?4。并证明：界n?1是紧的。 证：(反证法)

假设存在满足条件的n阶不连通图G。设G1,为n1,n2

则：

?(G)??(G)?(n1?1)?(n2?1)?n?2G2分别为G的两个子图，阶数分别

与条件矛盾。

2.14 证明：若图G的任意一条边都连接一个奇点和一个偶点，则G是二部图且有偶数条边。 证：以G中所有的奇点为元素作集合U；

以G中所有的偶点为元素作集合W

∵G中的每条边分别连一个奇点一个偶点

∴G的每条边必连接U中的一个顶点和W中的一个顶点 于是G是二部图，U和W为其的部集

2.16 证明：对于阶为2n?1(2n?1?5)的图G，若G的每个顶点的度或为n?1或为n?2，则G包含至少n?1个度为n?2的顶点或至少n?2个度为n?1的顶点。 证：（反正法）

假设G之多包含n个度为n+2的顶点，则其余n+1个点的度均为n+1 那么dG(v)?n(n?2)?(n?1)(n?1)?2n2+4n+1为奇数 这与图论第一定理矛盾

同理可证至少含有n+2个度为n+1的顶点

2.18 设8阶图G的顶点集为V(G)??v1,v2,?,v8?，若d试求degv8，egvi?i(1?i?7)，并给予解释。

解：由已知degv1?1,degv2?2,degv3?3,degv4?4,degv5?5,degv6?6,degv7?7 则可以得到下图：