در یک گراف $۳$ - منتظم از مرتبهی $n$، میدانیم که $\gamma (G)=۷$ است. $n$ برابر کدامیک از عددهای زیر میتواند باشد؟
برای احاطه شدن کل رأسها، $7$ رأس نیاز است، پس گراف حداقل $7$ رأس داشته و 1 غلط میشود. از طرفی گراف فردمنتظم مرتبهی فرد نداریم، پس $n=11$ هم نمیتواند باشد. $n=8$ هم نمیتواندباشد! چرا؟ ببینید یک رأس درجهی $3$، خودش و $3$ رأس دیگر را احاطه میکند، یعنی با انتخاب یک رأس، چهار رأس احاطه میشود. حالا اگر در بدترین حالت، تکتک هر $4$ رأس باقیماندهی دیگر $(8-4=4)$ را هم بگیریم، $\gamma (G)=5$ میشود. نه $7$! در حالت کلی، یک کران بالا برای $\gamma (G)$ بهصورت $\gamma (G)\le n-\Delta $ است. مثلاً اگر $n=8$ باشد، $\gamma (G)\le 8-3=5$ میشود، پس قطعاً $\gamma (G)$ برابر $7$ نمیشود. بنابراین 4 میتواند درست باشد.