Question

离散证明题： 在一个连通简单图中, 总存在度数相同的两个结点. 求教大神如何证明

求教此题如何解答

Answer 1

设连通简单图的结点个数为n, 故每个结点的度数为1,2，...,n-1共n-1种情形，但因为有n个结点，由抽屉原理，至少有两个结点度数相同。
那结论怎么不成立？
设x属于A∪C,那么x属于A或者C，x属于B或者D,故x属于B∪D
A∪C是B∪D的子集