به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
75 بازدید
در دبیرستان و دانشگاه توسط OXIDE

ثابت کنید به ازای هر گراف ساده $G$ که $p \geq 6$ لااقل یک دور به طول $m=3$ در $G$ و یا $ \bar{G} $ وجود دارد.

راهنمایی: $ \bar{G} $ مکمل گراف $G$ است.

توسط reza91
+1
@OXIDE
یک دفه کل کتاب رو میذاشتی
توسط OXIDE
+1
کل کتاب نیست مسله هایی است از منابع و جاهای مختلف که برام جای سوال شده

1 پاسخ

+1 امتیاز
توسط erfanm

راس دلخواهی مانند $ A $ را در نظر میگیریم دو حالت داریم یا وجود دارند سه راس مانند $B $و $ C$و$ D $ که با این راس در $ G $ وصل هستند یا اینکه حداکثر دو راس با این راس در $G $ وصل هستند اما چون حداقل $6$ راس داریم لذا سه راس باقی میماند که با $ A $ وصل نیستند یعنی در $ \overline{G} $ با این راس وصل هستند. پس می توان فرض کرد 3 راس مجاور با $A$ وجود دارد(در حالت دوم $ \overline{G} $ را همان گراف اولیه و $ G$ را مکمل گراف میگیریم)

حال اگر دو راس از این سه راس مجاور با $ A $، با هم وصل باشند آنگاه همراه $ A $ یک مثلث را تشکیل می دهند و حکم برقرار است. پس فرض کنیم هیچ دو تایی از این سه راس با هم وصل نباشند لذا در $ \overline{G} $ این سه با هم وصل هستند و باز حکم برقرار است.

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...