در گراف $G$ از مرتبهی $۱۰$، $\delta =۶$ است. کدام گزینه در مورد عددِ احاطهگریِ گرافِ مکملِ $G$، درست است؟ (بهترین کران پایین موردنظر است.)
مجموع درجهی یک رأس در خود گراف و گراف مکمل، برابر $p-1$ میشود. فرض کنیم ${{\deg }_{G}}(a)=\delta =6$ باشد، پس: $\underbrace{\deg (a)}_{6}+{{\deg }_{{\bar{G}}}}(a)=p-1=9\Rightarrow {{\deg }_{{\bar{G}}}}(a)=3$ رأس $a$ در خود گراف، دارای کمترین درجه است، پس در گراف مکمل، بیشترین درجه را دارد، این یعنی $\Delta $ در گراف مکمل، برابر $3$ میشود. حالا در گراف $\bar{G}$ داریم: $\gamma (\bar{G})\ge \left\lceil \frac{n}{\Delta +1} \right\rceil =\left\lceil \frac{10}{3+1} \right\rceil =3$