Question

证明：无向简单图中一定存在度数相同的两个结点．

Answer 1

【答案】：因为在n个结点的简单图的度序列(d₁，d₂，…，d_n)中，d₁≤d₂≤…≤d_n≤n-1，若d₁，d₂，…，d_n中没有两个相等，则(d₁，d₂，…，d_n)=(0，1，2，…，n-1)．删去G中的孤立结点v₀(deg(v₀)=0)，余下的子图G'有n-1个结点且存在度为n-1的结点，故G'不是简单图．这与前提矛盾，故d₁，d₂，…，d_n中至少存在两个相等的度数，即存在两个等度结点．