设d1 d2 … dn为n个互不相同的正整数证明不存在以d1 d2 … dn为度数列的无向简单图．

大学 2021-05-27 18:05:18 度数已帮助人

设d₁，d₂，…，d_n为n个互不相同的正整数，证明不存在以d₁，d₂，…，d_n为度数列的无向简单图．

难度★★☆ 搜索

利用n阶无向简单图G的最大度△(G)≤n-1证明本题．
用归谬法证明．假设存在以d1，d2，…，dn(d1，d2，…，dn为n个互不相同的正整数)为度数列的无向简单图G=〈V，E〉，V={v1，v2，…，vn}，不妨设d(vi)=di，i=1，2，…，n，则
△(G)=max{d(v1)，d(v2)，…，d(vn)}
=max{d1，d2，…，dn}≥n
这与n阶无向简单图的最大度应该≤n-1相矛盾．

设d1 d2 … dn为n个互不相同的正整数 证明不存在以d1 d2 … dn为度数列的无向简单图．