问答题 设G=(V,E)是一个简单图,令δ(G)=min{d(v)}(称δ(G)为G的最小次)。证明:(1)若δ(G)≥2,则G必有圈;(2)若δ(G)≥2,则G必有包含至少δ(G)+1条边的圈。
【正确答案】证  (1)由题设G(V,E)是简单图,即该图中无环,无重复边。由已知,δ(G)≥2,即G的最小边大于或等于2。假设G中无圈,则G可能为树或非连通图,对该两种情况均存在悬挂点,即min{d(v))=1,与δ1(G)≥2矛盾,故假设不成立,G必有圈。
   (2)若δ(G)≥2,设与δ(G)对应的点为vk,即vk必与δ(G)个端点相连。根据(1)结论,G中必有圈(由于圈中的连通图至少vk与这δ(G)个端点构成圈)。vi(i=1,2,…,δ(G))的次至少为δ(G),至少与δ(G)个端点相联。若vk与vi这δ(G)+1个端点不构成圈,则在端点处必向外延伸,对该圈而言,边数大于δ(G)+1条,故G必有包含至少δ(G)+1条边的圈。
【答案解析】