问答题
设d1,d2,…,dn为n个互不相同的正整数,证明不存在以d1,d2,…,dn为度数列的无向简单图.
【正确答案】利用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相矛盾.
【答案解析】