واضح است که حکم برای گرافهای طوقه دار درست نیست.گرافی با یک رأس $v$ و یک طوقه در نظر بگیرید.اگر عدد $0$ را نسبت دهیم آنگاه $s[v]=0$ و اگر عدد $1$ را نسبت دهیم $s[v]=2$.
حال حکم را برای گرافهای بدون طوقه اثبات می کنیم:
با توجه به اینکه هر گراف همبند دارای درخت فراگیر ماکسیمال (درخت گرافیست که شامل دور نیست و اگر شامل تمام رأسها باشد ماکسیمال نام دارد) است و هرگراف دارای تعدادی مؤلفه همبند است کافیت حکم را برای درختها انجام دهیم.این کار را با استقراء روی رأسها انجام می دهیم.
اگر یک رأس داشته باشیم عدد $1$ را به آن نسبت می دهیم و اگر دو رأس داشته باشیم $0$ را به یک رأس و $1$ را به رأس دیگر نسبت می دهیم.اگر سه رأس داشته باشیم عدد رأسها را $(0,1,0)$ یا $(1,0,1)$ بگیرید.پس حکم برای یک،دو و سه رأس درسته.
حالا فرض کنید حکم برای هر درخت با $n$ رأس درسته است و درختی را در نظر بگیرید که شامل $n+1$ رأس باشد.هر درختی دارای حداقل دو رأس با درجۀ یک است.یکی از این رأس را در نظر بگیرید و $v$ بنامید.به راحتی می توان نشان داد که $G-v$ درخت است که حکم برای آن درست است.حالا رأس $u$ را از $G-v$ طوری در نظر بگیرید(این رأس وجود دارد(؟)) که نزدیکترین رأس از نظر طول مسیر به $v$ باشد.اگر $0$ به $u$ نسبت داده شده باشد آنگاه عدد $1$ را به $v$ و اگر $1$ به $u$ نسبت داده شده باشد آنگاه $0$ را به $v$ نسبت دهید.با این نسبت دادن حکم ثابت است.
$ \Box $
