Question

证明：若G是一个简单图，且δ(G)≥|V|-2，则k(G)=δ(G)．

Answer 1

【答案】：因为G是简单图，所以每个顶点的度数最多为|V|-1，现δ(G)≥|V|-2，所以只要讨论以下两种情况即可．
①若δ(G)=|V|-1，则G=K_|v|，因此k(G)=|V|-1=δ(G)．
②若δ(G)=|V|-2，则必有两个结点不相邻接。设v₁，v₂∈V且v₁与v₂不相邻接．于是，对于任意的v₃∈V，都有v₁v₃，v₂v₃∈E．因此，对于V中任意的|V|-3个结点的集合V₁，G-V₁一定是连通的，故必有k(G)≥|V|-2=δ(G)．而易知k(G)≤δ(G)，所以k(G)=δ(G)．