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