Question

一道离散数学的图论题目，求详解，速度啊，亲，thax！！！

题目如下：
设无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点的度数均小于3，请问G中至少有几个定点？（答案是11）
请把详解，比如用到那些定理，计算过程写出来，急求，谢谢啦！！！

Answer 1

由握手定理可知：
共有2x16=32个度数。由于有3个4度，4个3度顶点。即有3x4+4x3=24个度数。
即余下顶点共有32-24=8个度数，那么接下来就考虑余下的有几个顶点：
因为其余顶点度数小于3，即是0、1或者2，即余下的最多是无穷个顶点，最少是4个顶点。
考虑到奇度数的顶点为偶数（4），所以上面可以是4个顶点，
即至少有4+4+3=11个顶点
希望能帮助你。。。。

Answer 2

这个很好理解，首先度数是什么概念呢，对于无向图度数就是这个点连了多少边，所以一个无向边是对首尾两个节点各贡献一个度数，所以16条边的无向图，节点总度数是32，减去3个4度节点和4个3度节点，还剩8个度数，其余节点的度数均不超过2，所以还剩至少4个节点哈哈，加起来是3个4度节点和4个3度节点和4个2度节点，至少11个节点，另外，通过画图确实得到了这样的图，所以证明出至少有11个节点。