Question

(2,3,3,5,5,6,6)是否是可简单图化的，如果是，请给出两个非同构的简单图，谢啦~ 关于离散数学的问题。

Answer 1

不可简单图化。
这个需要一边分析一边画图。假设7个顶点是a,b,c,d,e,f,g。根据度数之和30，边数是15。既然是简单图，每个顶点的度数都不超过6。
假设顶点a,b的度数是6，则a,b与其余的顶点都相邻，用掉11条边。现在剩下的5个顶点的度数都是2，假设c的度数最终是2，那么d,e,f,g的最终度数是3,3,5,5，还需要度数1,1,3,3，只能用4条边。单独考虑d,e,f,g，用4条边构建度数序列1,1,3,3，这是不可能的，因为1个3度顶点的存在使得另外3个顶点的度数是1，再加一条边构建3度顶点，则有2个点的度数是2，剩下一个1度顶点，所以度数序列只能是1,2,2,3。