در گراف $G$ از مرتبهی $۱۲$ داریم $\Delta =۶$. کدام گزینه درست است؟
از یک طرف، کران پایین $\gamma $ از رابطهی زیر بهدست میآید: $\gamma (G)\ge \left\lceil \frac{n}{\Delta +1} \right\rceil =\left\lceil \frac{12}{6+1} \right\rceil =2$ اما کران بالا برای $\gamma $؛ ببینید رأس $\Delta $، $6$ رأس دیگر را احاطه میکند و یکی هم خودش، پس با انتخاب رأس $\Delta $، دقیقاً $7$ رأس احاطه میشود. $5$ رأس دیگر باقی مانده است. همهی آنها به همراه $\Delta $ (یعنی $7$ رأس)، قطعاً کل رأسها را احاطه میکنند، یعنی در بدترین شرایط، این گراف با $6$ رأس احاطه میشود، پس $\gamma (G)\le 6$ . خوب است بدانید همواره $\gamma (G)\le n-\Delta $ .