پاسخ مسئله
برای حل این مسئله، ابتدا باید مفاهیم مربوط به پوشش گراف ($\gamma(G)$) و درجه حداکثر ($\bigtriangleup(G)$) را درک کنیم.
- پوشش گراف حداقل تعداد رئوس مورد نیاز برای پوشش تمام یالهای گراف است.
- درجه حداکثر، حداکثر درجه بین تمام رئوس گراف است.
ادعا شده است که برای هر گراف $G$ با $n$ رأس، نامساوی $\lceil { \frac{n}{1+ \bigtriangleup (G) }}\rceil \leq \gamma (G)$ برقرار است.
برای اثبات، فرض کنید $\bigtriangleup(G) = k$ باشد. این بدان معنی است که حداقل یک رأس با درجه $k$ وجود دارد.
حال، گراف را به $\lceil \frac{n}{k+1} \rceil$ زیرگراف (یا دسته) تقسیم میکنیم به طوری که هر زیرگراف حداکثر شامل $k+1$ رأس باشد.
در هر زیرگراف، حداقل یک رأس برای پوشش یالها لازم است. بنابراین، حداقل به $\lceil \frac{n}{k+1} \rceil$ رأس برای پوشش تمام یالهای گراف نیاز داریم.
از آنجایی که $\gamma(G)$ نشاندهنده حداقل تعداد رئوس لازم برای پوشش گراف است، داریم: $\lceil { \frac{n}{1+ \bigtriangleup (G) }}\rceil \leq \gamma (G)$
نتیجه
این اثبات نشان میدهد که ادعای مطرح شده صحیح است و حداقل پوشش گراف ($\gamma(G)$) بزرگتر یا مساوی با $\lceil { \frac{n}{1+ \bigtriangleup (G) }}\rceil$ است.
