图论及其应用徐俊明课后习题提示(11)

Byinductiononv≥1.AssumetheconclusionholdsforanydigraphwithorderlessthenvandletGbeadigraphwithorderv.Arbitrarilychoosex∈V(G).Thenbythe

+inductionhypothesis,inthesubdigraphG ({x}∪NG(x)),thereisanindependentset

+I suchthatdG(I ,y)≤2foranyy∈V(G)\I .Ifthereisu∈I suchthatx∈NG(x),

thendG(I,y)≤2foranyy∈V(G)\Iclearly.IfthereisnosuchavertexinI,thenxisnotadjacentwithanyvertexinI .Thus,I=I ∪{x}isanindependentsetrequired.

11

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库图论及其应用徐俊明课后习题提示(11)在线全文阅读。