例④(33,23)、⑤5,23,1,4)能成为图的 度数序列吗?为什么? ②已知图G中有10条边4个3度顶点其 余顶点的度数均不大于2,问G中至少 有多少个顶点?为什么 解:①由于这两个序列中奇数个数均为奇数 它们都不能成为图的度数序列。 ②图中边数m=10由握手定理可知G中各质 点度数之和为20,4个3度顶点占去12度 还剩8度若其余全是2度顶点还需要4个顶 点来占用这8度,所以G至少有8个顶点
例 ① (3,3,2,3),(5,2,3,1,4)能成为图的 度数序列吗？为什么？ ② 已知图G中有10条边,4个3度顶点,其 余顶点的度数均不大于2, 问G中至少 有多少个顶点? 为什么 ？ 解: ① 由于这两个序列中,奇数个数均为奇数, 它们都不能成为图的度数序列。 ② 图中边数m =10,由握手定理可知,G中各顶 点度数之和为20，4个3度顶点占去12度， 还剩8度若其余全是2度顶点,还需要4个顶 点来占用这8度，所以G至少有8个顶点
完全图 设G为n阶无向简单图,若G中每个顶点均与 的m-1个顶点相邻,则称G为m阶无向完全图,简称n阶 完全图,记作Kn(m21)。 如 Kn的边数为m=Cn2=m(n-1)2
如： K3 K6 Kn的边数为m = Cn 2= n(n-1)/2 完全图 设G为n阶无向简单图，若G中每个顶点均与其余 的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶 完全图，记作Kn (n≥1)
有向完全图 设D为n阶有向简单图,若D中每个顶点都邻接到 余的n-1个顶点,又邻接于其余的n-1个顶点,则称1 为n阶有向完全图。 如: 3阶有向完全图 n阶有向完全图的边数m=n(n-1)
如： 3阶有向完全图 n阶有向完全图的边数m=n(n-1）。 有向完全图 设D为n阶有向简单图，若D中每个顶点都邻接到其 余的n-1个顶点，又邻接于其余的n-1个顶点，则称D 为n阶有向完全图
正则图 在一个无向简单图中,如果每个结点的 度数均为k,则该图称为k正则图。 下图所示的图称为彼得森( Petersen)图,是 3-正则图。完全图是n-1正则图
正则图 在一个无向简单图中，如果每个结点的 度数均为k，则该图称为k-正则图。 下图所示的图称为彼得森（Petersen）图，是 3-正则图。完全图是n-1-正则图
补图 设G=<VE>为n阶无向简单图以V为顶点集 以所有使G成为完全圈K的添加边组成的集含 为边集的图,称为G的补图,记作G。 如 (1) (3)
如： (1) (3) 补图 设G=<V,E>为n阶无向简单图,以V为顶点集， 以所有使G成为完全图 Kn 的添加边组成的集合 为边集的图，称为G的补图，记作G。 (2)