哈工大集合论习题课-第五章-图的基本概念习题课(学生)(共13页).doc

精选优质文档-倾情为你奉上第五章 图的基本概念习 题 课 11. 画出具有 6、8、10、2n个顶点的三次图；是否有7个顶点的三次图？2. 无向图有21条边，12个3度数顶点，其余顶点的度数均为2，求的顶点数。解：设图的顶点为，根据握手定理：，有，得。3. 下列各无向图中有几个顶点？（1）16条边，每个顶点的度为2；（2）21条边，3个4度顶点，其余的都为3度数顶点；（3）24条边，各顶点的度数相同。解： 设图的顶点为，根据握手定理：（1），即；所以，即有16个顶点。（2），即，所以。（3）各点的度数为，则，即，于是 若，； 若，； 若，； 若，； 若，； 若，； 若，； 若，； 若，； 若，。4设图中9个顶点，每个顶点的度不是5就是6。证明中至少有5个6度顶点或至少有6个5度顶点。证：由握手定理的推论可知，中5度顶点数只能是0，2，6，8五种情况，此时6度顶点数分别为9，7，5，3，1个。以上五