تعداد رأس‌های فرد و زوج: ریاضیات گسسته، فصل ۲

ایده

مجموع درجه‌ها زوج است. رأس‌های زوج به این مجموع عددی زوج می‌دهند، پس مجموع درجهٔ رأس‌های فرد هم زوج است، و مجموعِ چند عدد فرد فقط وقتی زوج است که تعدادشان زوج باشد. پس تعداد رأس‌های فرد هر گراف زوج است. دربارهٔ رأس‌های زوج چنین چیزی نداریم؛ زوجیت تعدادشان همان زوجیت مرتبهٔ گراف است.

نمونهٔ نهایی

نهایی خرداد ۱۳۹۹، سؤال ۱۷۱ نمره

ثابت کنید تعداد رأس‌های فرد هر گراف، عددی زوج است.

رأس‌ها را به دو دستهٔ فرد $A$ و زوج $B$ تقسیم کن و مجموع درجه‌ها را هم به همین دو بخش بشکن.۰/۲۵ نمره
$v \in V (G) \sum de g (v) = v \in A \sum de g (v) + v \in B \sum de g (v)$
کل مجموع برابر $۲ q$ است و مجموع روی $B$ هم زوج است، چون درجهٔ هر رأس $B$ زوج است.۰/۲۵ نمره
$v \in V (G) \sum de g (v) = ۲ q, v \in B \sum de g (v) = ۲ k$
مجموع درجه‌های رأس‌های فرد تفاضل دو عدد زوج است، پس زوج است.۰/۲۵ نمره
$v \in A \sum de g (v) = ۲ q - ۲ k = ۲ (q - k)$
مجموعِ چند عدد فرد فقط وقتی زوج است که تعدادشان زوج باشد، پس $n (A)$ زوج است.۰/۲۵ نمره

همهٔ سؤال‌های این تیپ

امتحان نهایی ۸

۲ سؤال دیگر