Question

无向图G有十二条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点

Answer 1

由握手定理，2*12得x>8。所以G中至少有9个结点。

在无向图中:一条边（x,y）与（y,x）表示的结果相同，用圆括号表示。

对以图的顶点表示信息收发中心，边表示通信链的无向图为基础，分析了无向图直径的一些特性 ,从而对通信网的可靠性加以研究。得到了一个通信网即无向图在去掉若干条边后，其直径的长度仍保持不变的一个必要充分条件，并对相应的必要条件和充分条件分别进行探讨，得到一些有益的结果。

扩展资料：

注意事项：

假设无向图G采用邻接矩阵存储，求出图G最大度值并输出顶点的编号（有多个结果的都要输出）。

判断一个图的连通性，从概念上来说，就是如果一个图是连通的，那么对于图上面的任意两个节点i，j来说，相互之间可以通过某个路径连接到对方。

任意的两个节点都可以通过一个路径到达对方。而对于非连通的图来说，相当于将一个图分割成多个独立的部分，每个部分之间没有任何联系。

参考资料来源：百度百科-无向图

Answer 2

设G中有x个结点，则度数小于3的结点有x-6个，由握手定理，
2×12<6×3+3(x-6)。
得x>8。
所以G中至少有9个结点。