请问结点度数列为1...n-1为什么后面就与G′是简单图矛盾了呀

Question

请问结点度数列为1...n-1为什么后面就与G′是简单图矛盾了呀？

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

在这个问题中，我们首先将人与结点进行对应，在人之间有朋友关系的情况下，对应的结点之间就会有边相连，从而形成一个图G。我们需要证明，在图G中存在度数相等的结点。

假设图G有n个结点。如果图G中不存在度数相等的结点，那么根据简单图的定义，图G的结点度数序列应为：1, 2, ..., n-1。

我们可以思考一下，如果我们删除掉度数为0的结点后得到的图G'仍然是简单图，那么它的结点度数序列应该是什么呢？

我们可以发现，删去度数为0的结点后，图G'的结点度数序列应为：1, 2, ..., n-2。而根据题目给出的结点度数序列为1, 2, ..., n-1，显然与图G'的结点度数序列不一致。

因此，我们可以得出结论：在图G中必然存在度数相等的结点。

具体证明步骤可分为以下几步：

1. 假设图G有n个结点，且不存在度数相等的结点。
2. 根据简单图的定义，图G的结点度数序列应为：1, 2, ..., n-1。
3. 删除度数为0的结点后得到的图G'的结点度数序列应为：1, 2, ..., n-2。
4. 由于题目给出的结点度数序列为1, 2, ..., n-1, 与图G'的结点度数序列不一致。
5. 因此，假设不成立，图G中必然存在度数相等的结点。

综上所述，可以得出结论：在任何两个或两个以上的组内，存在两个人在组时有相同数的朋友。