列各组数中，那些能构成无向图的度数列那些能构成无向简单图的度数列
（1）1，1，1，2，3
（2）2，2，2，2，2
（3）3，3，3，3
（4）1，2，3，4，5
（5）1，3，3，3
解答：（1），（2），（3），（5）能构成无向图的度数列。
（1），（2），（3）能构成五项简单图的度数列。
设有向简单图D 的度数列为2，2，3，3，入度列为0，0，2，3，试求D 的出度列。 解：因为 出度=度数-入度，所以出度列为2，2，1，0。
设D 是4阶有向简单图，度数列为3，3，3，3。它的入度列（或出度列）能为1，1， 1，1吗
解：由定理可知，有向图的总入度=总出度。该有向图的总入度=1+1+1+1=4,总出度=2+2+2+2=8,4！=8，所以它的出度列（或入度列）不能为1，1，1，1。
35条边，每个顶点的度数至少为3的图最多有几个顶点
解：根据握手定理，所有顶点的度数之和为70，假设每个顶点的度数都为3，则 n 为小于等于3
70的最大整数，即：２３ ∴ 最多有23个顶点
7.7 设n 阶无向简单图G 中，δ（G ）=n-1，问△（G ）应为多少
解： 假设n 阶简单图图n 阶无向完全图，在K n 共有
2)1(-n n 条边，各个顶点度数之和为n （n-1）
∴每个顶点的度数为n
n n )1(-=n-1 ∴△（G ）=δ（G ）=n-1
一个n （n ≥２）阶无向简单图Ｇ中，n 为奇数，有r 个奇度数顶点，问Ｇ的补图G 中有几个奇度顶点
解：在K n 图中，每个顶点的度均为（n-1），n 为奇数，在Ｇ中度为奇数的顶点在G 中仍然为奇数，
∴共有r 个奇度顶点在G 中
７.９ 设Ｄ是n 阶有向简单图，Ｄ’是Ｄ的子图，已知Ｄ’的边数m ’＝n （n-1），问Ｄ的边数m 为多少
解： 在Ｄ’中m ’＝n （n-1） 可见Ｄ’为有个n 阶有向完全图，则Ｄ＝Ｄ’ 即Ｄ’就是Ｄ本身，
∴m=n （n-1）
有向图D 入图所示。求D 中长度为4 的通路总数，并指出其中有多少条是回路
又有几条是V3到V4的通路
答: D中长度为四的通路总数：15
其中有3条是回路
2条是V3到V4的通路
评语：此题的结果是对的，但是应该写出求解过程，即：先写出邻接矩阵A，然后求A的四次幂，通过矩阵指出通路或回路的条数。
设n阶图G中有m条边，每个顶点的度不是k就是k+1，若G中有N k个k度顶点，N k+1个(k+1)度顶点，则N k为
解: 由题义可以得到: N k*k+ N k+1*(k+1)=2m ①握手定理
N k+ N k+1=n ②n阶图
由①②解得N k=n*(k+1)-2m
