شاه کلید نکات
شاه کلید سوال
یک جمع 7 نفره از دانش آموزان یک کلاس را در نظر بگیرید. فرض کنید دوستی بین اعضای این گروه یک رابطه دوطرفه است، یعنی هر دو نفر از آنها یا هر دو با هم دوستاند و یا هیچیک با دیگری دوست نیست. اکنون:
الف گراف 7 رأسی G را تشکیل دهید به این صورت که به ازای هر دانش آموز یک رأس قرار دهید، سپس هر دو رأس را به هم وصل کنید اگر و تنها اگر دانش آموزان متناظر با آن دو رأس با هم دوست باشند.
ب با استفاده از قضیه قبل نشان دهید که امکان ندارد درجه تمام رئوس گراف حاصل برابر با 3 باشد.
پ با توجه به مراحل قبل و با استفاده از گراف نشان دهید که اگر تعداد افراد یک جمع عددی فرد باشد امکان ندارد تمام نفرات آن جمع، دارای تعداد فردی دوست در آن جمع باشند.
الف
ب
اگر درجه تمام رئوس گراف حاصل 3 باشد، آن گاه مجموع درجات رئوس 21=7×3 خواهد شد که عددی فرد است و با قضیه تناقض دارد، زیرا باید مجموع درجات رئوس عددی زوج باشد.
پ
اگر تمام نفرات جمعِ فرد نفری، دارای فرد تا دوست باشد، یعنی در یک گراف تعداد رئوس درجه فرد، فرد است که با نتیجه گرفته شده از قضیه (بالای صفحه) تناقض دارد. لذا چنین موردی امکان پذیر نیست.
1736019749.png)
