离散数学习题解答(第五章)格与布尔代数

离散数学第2版课后习题答案离散数学是计算机科学和数学领域中一门重要的学科，它研究离散对象及其关系、结构和运算方法。

离散数学的应用非常广泛，包括计算机科学、信息科学、密码学、人工智能等领域。

而离散数学第2版是一本经典的教材，它系统地介绍了离散数学的基本概念、原理和方法。

本文将为读者提供离散数学第2版课后习题的答案，帮助读者更好地理解和掌握离散数学的知识。

第一章：基本概念和原理1.1 命题逻辑习题1：命题逻辑的基本符号有哪些？它们的含义是什么？答：命题逻辑的基本符号包括命题变量、命题联结词和括号。

命题变量用字母表示，代表一个命题。

命题联结词包括否定、合取、析取、条件和双条件等，分别表示“非”、“与”、“或”、“如果...则...”和“当且仅当”。

括号用于改变命题联结词的优先级。

习题2：列举命题逻辑的基本定律。

答：命题逻辑的基本定律包括德摩根定律、分配律、结合律、交换律、吸收律和否定律等。

1.2 集合论习题1：什么是集合？集合的基本运算有哪些？答：集合是由一些确定的对象组成的整体，这些对象称为集合的元素。

集合的基本运算包括并、交、差和补等。

习题2：列举集合的基本定律。

答：集合的基本定律包括幂等律、交换律、结合律、分配律、吸收律和德摩根定律等。

第二章：数理逻辑2.1 命题逻辑的推理习题1：什么是命题逻辑的推理规则？列举几个常用的推理规则。

答：命题逻辑的推理规则是用来推导命题的逻辑规则。

常用的推理规则包括假言推理、拒取推理、假言三段论和析取三段论等。

习题2：使用推理规则证明以下命题：如果A成立，则B成立；B不成立，则A不成立。

答：假言推理规则可以用来证明该命题。

根据假言推理规则，如果A成立，则B成立。

又根据假言推理规则，如果B不成立，则A不成立。

2.2 谓词逻辑习题1：什么是谓词逻辑？它与命题逻辑有何区别？答：谓词逻辑是一种扩展了命题逻辑的逻辑系统，它引入了谓词和量词。

与命题逻辑不同，谓词逻辑可以对个体进行量化和描述。

第十四章部分课后习题参考答案5、设无向图G 有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 至少有多少个顶点？在最少顶点的情况下，写出度数列、)()(G G δ、∆。

解：由握手定理图G 的度数之和为：20102=⨯3度与4度顶点各2个，这4个顶点的度数之和为14度。

其余顶点的度数共有6度。

其余顶点的度数均小于3，欲使G 的顶点最少，其余顶点的度数应都取2, 所以，G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2,2)(,4)(==∆G G δ.7、设有向图D 的度数列为2，3，2，3，出度列为1，2，1，1，求D 的入度列，并求)(),(D D δ∆，)(),(D D ++∆δ,)(),(D D --∆δ.解：D 的度数列为2，3，2，3，出度列为1，2，1，1，D 的入度列为1,1,1,2.2)(,3)(==∆D D δ,1)(,2)(==∆++D D δ,1)(,2)(==∆--D D δ8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？解：由握手定理图G 的度数之和为：1262=⨯设2度点x 个，则1221513=+⨯+⨯x ，2=x ，该图有4个顶点.14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。

(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化；18、设有3个4阶4条边的无向简单图G 1、G 2、G 3，证明它们至少有两个是同构的。

证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。

但3，3，1，1对应的图不是简单图。

所以从同构的观点看，4阶4条边的无向简单图只有两个：所以，G 1、G 2、G 3至少有两个是同构的。

离散数学第五章习题答案题目1: 定义一个关系R在集合A上，如果对于所有的a, b, c属于A，满足以下条件：- 如果(a, b)属于R，则(b, a)属于R。

- 如果(a, b)属于R且(b, c)属于R，则(a, c)属于R。

证明R是传递的。

答案：根据题目给出的条件，R是对称的和传递的。

首先，对称性意味着如果(a, b)属于R，那么(b, a)也必须属于R。

其次，传递性意味着如果(a, b)和(b, c)都属于R，那么(a, c)也必须属于R。

结合这两个性质，我们可以得出结论：对于任意的a, b, c属于A，如果(a, b)和(b, c)都属于R，那么(a, c)也属于R，从而证明了R的传递性。

题目2: 给定一个函数f: A → B，如果对于A中的每个元素a，都有唯一的b属于B使得f(a) = b，那么称f为单射（或一一映射）。

证明如果函数f是单射，那么它的逆函数f^-1也是单射。

答案：要证明f^-1是单射，我们需要证明对于B中的任意两个元素b1和b2，如果f^-1(b1) = f^-1(b2)，则b1 = b2。

假设f^-1(b1) = a且f^-1(b2) = a'，其中a, a'属于A。

由于f是单射，我们知道f(a) = b1且f(a') = b2。

根据f^-1的定义，我们有b1 = f(a) = f(a') = b2。

因此，如果f^-1(b1) = f^-1(b2)，则b1必须等于b2，这证明了f^-1是单射。

题目3: 证明一个函数f: A → B是满射（或到上映射）当且仅当对于B中的每个元素b，都存在A中的元素a使得f(a) = b。

答案：首先，我们证明如果f是满射，那么对于B中的每个元素b，都存在A 中的元素a使得f(a) = b。

假设f是满射，这意味着B中的每个元素都是A中某个元素的像。

因此，对于B中的任意元素b，我们可以找到一个a属于A，使得f(a) = b。

页眉内容《离散数学》试题及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）PP⌝P→⌝↔（4）QQ→⌝（2）QP⌝→（3）Q8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

第二版高等教育出版社课后答案第一章部分课后习题参考答案16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0.（3）（⌝p∧⌝q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1）↔ (0∧0∧0)⇔0(4)（⌝r∧s）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔117．判断下面一段论述是否为真：“π是无理数。

并且，如果3是无理数，则2也是无理数。

另外6能被2整除，6才能被4整除。

”答：p: π是无理数 1q: 3是无理数0r: 2是无理数 1s:6能被2整除 1t: 6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。

19．用真值表判断下列公式的类型：（4）(p→q) →(⌝q→⌝p)（5）(p∧r) ↔(⌝p∧⌝q)（6）((p→q) ∧(q→r)) →(p→r)答：（4）p q p→q ⌝q ⌝p ⌝q→⌝p (p→q)→(⌝q→⌝p)0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 1 0 0 1 1所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) ⌝(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)⇔(⌝p∨(p∨q))∨(⌝p∨r)⇔⌝p∨p∨q∨r⇔1所以公式类型为永真式(3)P q r p∨q p∧r （p∨q）→(p∧r)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可满足式4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)⇔(p→(q∧r))(4)(p∧⌝q)∨(⌝p∧q)⇔(p∨q) ∧⌝(p∧q)证明（2）(p→q)∧(p→r)⇔ (⌝p∨q)∧(⌝p∨r)⇔⌝p∨(q∧r))⇔p→(q∧r)（4）(p∧⌝q)∨(⌝p∧q)⇔(p∨(⌝p∧q)) ∧(⌝q∨(⌝p∧q)⇔(p∨⌝p)∧(p∨q)∧(⌝q∨⌝p) ∧(⌝q∨q)⇔1∧(p∨q)∧⌝(p∧q)∧1⇔(p∨q)∧⌝(p∧q)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(⌝p→q)→(⌝q∨p)(2)⌝(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(⌝p →q)→(⌝q ∨p)⇔⌝(p ∨q)∨(⌝q ∨p)⇔(⌝p ∧⌝q)∨(⌝q ∨p)⇔ (⌝p ∧⌝q)∨(⌝q ∧p)∨(⌝q ∧⌝p)∨(p ∧q)∨(p ∧⌝q)⇔ (⌝p ∧⌝q)∨(p ∧⌝q)∨(p ∧q)⇔320m m m ∨∨⇔∑(0,2,3)主合取范式：(⌝p →q)→(⌝q ∨p)⇔⌝(p ∨q)∨(⌝q ∨p)⇔(⌝p ∧⌝q)∨(⌝q ∨p)⇔(⌝p ∨(⌝q ∨p))∧(⌝q ∨(⌝q ∨p))⇔1∧(p ∨⌝q)⇔(p ∨⌝q) ⇔ M 1⇔∏(1)(2) 主合取范式为：⌝(p →q)∧q ∧r ⇔⌝(⌝p ∨q)∧q ∧r⇔(p ∧⌝q)∧q ∧r ⇔0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为：(p ∨(q ∧r))→(p ∨q ∨r)⇔⌝(p ∨(q ∧r))→(p ∨q ∨r)⇔(⌝p ∧(⌝q ∨⌝r))∨(p ∨q ∨r)⇔(⌝p ∨(p ∨q ∨r))∧((⌝q ∨⌝r))∨(p ∨q ∨r))⇔1∧1⇔1所以该式为永真式.永真式的主合取范式为 1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统P中构造下面推理的证明：(2)前提：p→q,⌝(q∧r),r结论：⌝p(4)前提：q→p,q↔s,s↔t,t∧r结论：p∧q证明：（2）①⌝(q∧r) 前提引入②⌝q∨⌝r ①置换③q→⌝r ②蕴含等值式④r 前提引入⑤⌝q ③④拒取式⑥p→q 前提引入⑦￢p（3）⑤⑥拒取式证明（4）：①t∧r 前提引入②t ①化简律③q↔s 前提引入④s↔t 前提引入⑤q↔t ③④等价三段论⑥（q→t）∧(t→q) ⑤置换⑦（q→t）⑥化简⑧q ②⑥假言推理⑨q→p 前提引入⑩p ⑧⑨假言推理(11)p∧q ⑧⑩合取15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q结论：s→r证明①s 附加前提引入②s→p 前提引入③p ①②假言推理④p→(q→r) 前提引入⑤q→r ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p证明：①p 结论的否定引入②p→﹁q 前提引入③﹁q ①②假言推理④￢r∨q 前提引入⑤￢r ④化简律⑥r∧￢s 前提引入⑦r ⑥化简律⑧r∧﹁r ⑤⑦合取由于最后一步r∧﹁r 是矛盾式,所以推理正确.第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1) 对于任意x,均有2=(x+)(x).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x): 2=(x+)(x).G(x): x+5=9.(1)在两个个体域中都解释为)∀，在（a）中为假命题，在(b)中为真命题。

离散数学第二版最全课后习题答案详解离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、电气工程等领域都有着广泛的应用。

对于学习离散数学的同学们来说，课后习题的解答是巩固知识、加深理解的重要环节。

本文将为您提供离散数学第二版的最全课后习题答案详解，希望能对您的学习有所帮助。

在开始讲解具体的习题答案之前，让我们先简要回顾一下离散数学的主要内容。

离散数学包括集合论、数理逻辑、图论、代数结构等几个部分。

集合论是离散数学的基础，它研究集合的性质、运算和关系。

在集合论的习题中，常见的问题包括集合的表示、集合的运算（并集、交集、补集等）、集合的包含关系以及集合的基数等。

例如，有这样一道习题：设集合 A ＝｛1, 2, 3}，B ＝｛2, 3, 4}，求 A ∪ B 和A ∩ B。

答案是：A ∪ B ＝｛1, 2, 3, 4}，A ∩ B ＝｛2, 3}。

这是因为并集是包含两个集合中所有元素的集合，而交集是同时属于两个集合的元素组成的集合。

数理逻辑是研究推理和证明的工具，它包括命题逻辑和谓词逻辑。

在数理逻辑的习题中，需要掌握命题的符号化、逻辑公式的等价变换、推理规则的应用等。

比如，给出这样一个命题：“如果今天下雨，那么我就不去公园”，将其符号化。

我们可以设“今天下雨”为 P，“我去公园”为 Q，那么这个命题可以符号化为P → ¬Q。

图论是研究图的性质和应用的分支。

图的概念在计算机网络、交通运输等领域有着重要的应用。

图论的习题常常涉及图的表示、顶点的度、路径、连通性、图的着色等问题。

假设有这样一道题：一个无向图有 10 个顶点，每个顶点的度都为 6，求这个图的边数。

根据顶点度数之和等于边数的两倍这个定理，我们可以计算出边数为 30。

代数结构则包括群、环、域等概念，在这部分的习题中，需要理解和运用代数结构的定义和性质来解决问题。

接下来，我们具体来看一些习题的详细解答。

例 1：设集合 A ＝｛x ｜ x 是小于 10 的正奇数}，B ＝｛x ｜ x 是小于 10 的正偶数}，求 A B。

《离散数学》课后习题答案《离散数学》简介1、集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数2、图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用3、代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4、组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理5、数理逻辑部分：命题逻辑、一阶谓词演算、消解原理离散数学被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。

教学方式以课堂讲授为主，课后有书面作业、通过学校网络教学平台发布课件并进行师生交流。

《离散数学》学科内容随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

离散数学是传统的逻辑学，集合论(包括函数)，数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数(包括代数系统，群、环、域等)，布尔代数，计算模型(语言与自动机)等汇集起来的一门综合学科。

离散数学的应用遍及现代科学技术的诸多领域。

离散数学也可以说是计算机科学的基础核心学科，在离散数学中的有一个著名的典型例子-四色定理又称四色猜想，这是世界近代三大数学难题之一，它是在1852年，由英国的一名绘图员弗南西斯格思里提出的，他在进行地图着色时，发现了一个现象，“每幅地图都可以仅用四种颜色着色，并且共同边界的国家都可以被着上不同的颜色”。

离散数学课后习题答案离散数学课后习题答案离散数学是计算机科学中的一门重要课程，它涵盖了诸多数学概念与技巧，为计算机科学的理论基础打下了坚实的基础。

在学习离散数学的过程中，课后习题是巩固知识、提高能力的重要途径。

然而，有时候我们会遇到一些难以解答的问题，需要参考一些答案来进行思考与学习。

本文将为大家提供一些离散数学课后习题的答案，希望能对大家的学习有所帮助。

一、集合论1. 设A={1,2,3}，B={2,3,4}，求A∪B和A∩B的结果。

答案：A∪B={1,2,3,4}，A∩B={2,3}。

2. 证明：任意集合A和B，有(A-B)∪(B-A)=(A∪B)-(A∩B)。

答案：首先，对于任意元素x，如果x属于(A-B)∪(B-A)，那么x属于A-B或者x属于B-A。

如果x属于A-B，那么x属于A∪B，但x不属于A∩B；如果x属于B-A，同样有x属于A∪B，但x不属于A∩B。

所以(A-B)∪(B-A)属于(A∪B)-(A∩B)。

另一方面，对于任意元素x，如果x属于(A∪B)-(A∩B)，那么x属于A∪B，但x不属于A∩B。

所以x属于A或者x属于B。

如果x属于A，但x不属于B，那么x属于A-B；如果x属于B，但x不属于A，那么x属于B-A。

所以x属于(A-B)∪(B-A)。

所以(A∪B)-(A∩B)属于(A-B)∪(B-A)。

综上所述，(A-B)∪(B-A)=(A∪B)-(A∩B)。

证毕。

二、逻辑与证明1. 证明：如果p为真命题，那么¬p为假命题。

答案：根据命题的定义，命题要么为真，要么为假，不存在其他情况。

所以如果p为真命题，那么¬p为假命题。

2. 证明：对于任意整数n，如果n^2为偶数，则n为偶数。

答案：假设n为奇数，即n=2k+1（k为整数）。

那么n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1。

根据偶数的定义，2(2k^2+2k)为偶数，所以n^2为奇数。

离散数学习题解答习题五（第五章 格与布尔代数）1．设〈L ，≼〉是半序集，≼是L 上的整除关系。

问当L 取下列集合时，〈L ，≼〉是否是格。

a) L={1，2，3，4，6，12}b) L={1，2，3，4，6，8，12}c) L={1，2，3，4，5，6，8，9，10}[解] a) 〈L ，≼〉是格，因为L 中任两个元素都有上、下确界。

b) 〈L ，≼〉不是格。

因为L 中存在着两个元素没有上确界。

例如：812=LUB{8，12}不存在。

126312 4c) 〈L ，≼〉不是格。

因为L 中存在着两个元素没有上确界。

倒例如：46=LUB{4，6}不存在。

2．设A ，B 是两个集合，f 是从A 到B 的映射。

证明：〈S ，⊆〉是〈2B，⊆〉的子格。

其中S={y|y=f (x)，x ∈2A }[证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈B ∧(x)(x 863 124 12 10 84 2 6 973 1 5 10∈A1∧f (x)=y)}⊆B 所以B1∈2B，故此S⊆2B；又B0=f (A)∈S (因为A∈2A)，所以S非空；对于任何B1，B2∈S，存在着A1，A2∈2A，使得B1=f (A1)，B2=f (A2)，从而L∪B{B1，B2}=B1∪B2=f (A1)f (A2)=f (A1∪A2) （习题三的8的1））由于A1∪A2⊆A，即A1∪A2∈2A，因此f (A1∪A2)∈S，即上确界L∪B{B1，B2}存在。

对于任何B1，B2∈S，定义A1=f –1(B1)={x|x∈A∧f (x)∈B1}，A2=f-1(B2)={x|x∈A∧f (x)∈B2}，则A1，A2∈2A，且显然B1=f (A1)，B2=f (A2)，于是GLB{B1，B2}=B1∩B2=f (A1)∩f (A2)⊇f (A1∩A2) （习题三的8的2））又若y∈B1∩B2，则y∈B，且y∈B2。

5.1习题参考答案1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。

阮允准同学提供答案:解：设度数小于3的结点有x个，则有3×4＋4×3＋2x≥2×16解得：x≥4所以度数小于3的结点至少有4个所以G至少有11个结点2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。

阮允准同学答案：证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。

若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。

若度数为5的结点数为6,8个，结论显然成立。

由上可知，G中至少有5个6度点或至少有6个5度点。

3、证明：简单图的最大度小于结点数。

阮同学认为题中应指定是无向简单图.晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n.4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3 。

阮同学给出证明如下：证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。

所以结论成立。

5、试证明下图中两个图不同构。

晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。

我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。

6、画出所有5个结点3条边，以及5个结点7条边的简单图。

解：如下图所示： (晓津与阮同学答案一致)7、证明：下图中的图是同构的。

证明如下：在两图中我们可以看到有a→e,b→h,c→f,d→g两图中存在结点与边的一一对应关系，并保持关联关系。