با اضافه كردن ۱۸ يال به يک گراف ۴- منتظم، گرافی كامل حاصل میشود. اگر $a$ رأسی ازگراف كامل باشد، مجموعۀ ${{N}_{G}}=\left[ a \right]$ چند عضو دارد؟
نکتهٔ 1: در هر گراف کامل ${{k}_{p}}$ داریم: $q=\frac{p(p-1)}{2},\delta =\Delta =p-1$ نکتهٔ 2: در هر گراف $-k$ منتظم مرتبهٔ $p$ داریم: $2q=pk,\delta =\Delta =k$ با توجه به نكات داريم: $\frac{4p}{2}+18=\frac{p(p-1)}{2}\Rightarrow 4p+36={{p}^{2}}-p\Rightarrow {{p}^{2}}-5p- 36=0\Rightarrow (p-9)(p+4)=0\Rightarrow \left\{ \begin{matrix} p=9 \\ p=-4 \\ \end{matrix} \right.$ در گراف کامل ${{k}_{9}}$ درجۀ هر رأس ۸ است، يعنی هر رأس ۸ همسايه دارد و در نتيجه مجموعه همسايگی بستۀ رأس $a$ دارای ۹ عضو است. $\left| {{N}_{G}}\left[ a \right] \right|=9$ بنابراين گزينۀ ۱ پاسخ است. صفحههای ۳۵ تا ۴۰ رياضيات گسسته