سوال مورد نظر پیوست شده است
ممنون از دوستان
سلام. وقت بخیر.
این سوال مشکل داره.
برای رد گزینه ۱ میتونید یه درخت ۴ راسی به شکل Y درنظر بگیرید. حالا سه تا برگ رو به هم وصل کنید. ۷ تا دور داریم.
گزینه ۲ قابل اثباته. درخت یه گراف مسطحه که به ازای n راس، n-1 یال داره. اگه ۳ یال اضافه بشه میشه n+2 یال.
حداقل تعداد یال برای مسطح نبودن تو گرافهای K3,3 و K5 هست که حداقل ۳ یال بیشتر از تعداد رئوسشون دارن. (اولی ۶ راس و ۹ یال و دومی ۵ راس و ۱۰ یال دارن) پس اگه یه گراف همبند باشه و قراره مسطح نباشه، حداقل باید ۳ یال بیشتر از تعداد رئوسش داشته باشه.
گزینه ۳ که با مثال رد میشه. یه گراف به شکل مسیر درنظر بگیرید. (دو راس از درجه ۱ داشته باشیم) حالا چند یال بهش اضافه کنید که باز هم دو راس از درجه ۱ داشته باشیم. تعداد مسیرها بین اون دو راس درجه ۱ میتونه بیشتر از ۴ باشه.
گزینه ۴ هم نادرسته. وقتی به درخت چند یال اضافه کنیم، طول مسیرها زیاد نمیشه و فقط میتونه کمتر بشه