Question

اگر $G$ یک گراف ساده با $p$ گره و $q$ یال و کمینه‌درجهٔ $\delta$ باشد، آنگاه ثابت کنید که $q\leq\delta+\binom{p-1}{2}$.

Answer 1

راسی را با کمترین درجه در گراف در نظر می گیریم در بین $p-1$ راس باقیمانده حداکثر${p-1 \choose{2} }$ یال موجود است و راسی که ما انتخاب کردیم با $\delta$ یال با این مجموعه $p-1$ راسی وصل است لذا حداکثر یال در گراف برابر است با:$\delta +{p-1 \choose{2} }$ پس $$q \leq \delta +{p-1 \choose{2} }$$