شاه کلید نکات
شاه کلید سوال
قضیه: اگر G یک گراف با مرتبه p و اندازهq و\(V = \left\{ {{v_1}\;,\;{v_2}\;,\;...\;,\;{v_P}} \right\}\) مجموعه رئوس آن باشند، آنگاه:
\(\sum\limits_{i = 1}^P {\deg \;{v_i} = 2q} \)
نتیجه: تعداد رأس های فرد هر گراف، عددی زوج است.
اثبات: فرض کنیم G یک گراف و A مجموعه همه رئوس فرد گراف G و B مجموعه همه رئوس زوج گراف G باشد. در این صورت داریم \(\sum\limits_{v \in V\left( G \right)}^{} {\deg \left( v \right)} = \sum\limits_{v \in A}^{} {\deg \left( v \right)} + \sum\limits_{v \in B}^{} {\deg \left( v \right)} \)
از طرفی \(\sum\limits_{v \in B}^{} {\deg \left( v \right)} \;,\;\sum\limits_{v \in V\left( G \right)}^{} {\deg \left( v \right)} \) زوج اند. (چرا؟) بنابراین\(\sum\limits_{v \in A}^{} {\deg \left( v \right)} \) نیز عددی زوج است و این نتیجه می دهد که (n(A عددی زوج است. (چرا؟)
(چرای اول)
طبق قضیه مجموع درجات رئوس، زوج می باشد؛ پس\(\sum\limits_{v \in V(G)} {\deg (v)} \) زوج است.
از طرفی هر رأس B عددی زوج است و مجموع چند عدد زوج، عددی زوج است، لذا\(\sum\limits_{v \in B} {\deg (v)} \) زوج می باشد.
(چرای دوم)
درجه هر رأس A فرد باشد، لذا باید تعداد آن ها زوج باشد تا مجموع درجات عددی زوج شود.
1736019749.png)
