تالار گفتمان مانشت

سوال مورد نظر پیوست شده است

ممنون از دوستان

سلام. وقت بخیر.
این سوال مشکل داره.

برای رد گزینه 1 میتونید یه درخت 4 راسی به شکل Y درنظر بگیرید. حالا سه تا برگ رو به هم وصل کنید. 7 تا دور داریم.

گزینه 2 قابل اثباته. درخت یه گراف مسطحه که به ازای n راس، n-1 یال داره. اگه 3 یال اضافه بشه میشه n+2 یال.
حداقل تعداد یال برای مسطح نبودن تو گرافهای K3,3 و K5 هست که حداقل 3 یال بیشتر از تعداد رئوسشون دارن. (اولی 6 راس و 9 یال و دومی 5 راس و 10 یال دارن) پس اگه یه گراف همبند باشه و قراره مسطح نباشه، حداقل باید 3 یال بیشتر از تعداد رئوسش داشته باشه.

گزینه 3 که با مثال رد میشه. یه گراف به شکل مسیر درنظر بگیرید. (دو راس از درجه 1 داشته باشیم) حالا چند یال بهش اضافه کنید که باز هم دو راس از درجه 1 داشته باشیم. تعداد مسیرها بین اون دو راس درجه 1 میتونه بیشتر از 4 باشه.

گزینه 4 هم نادرسته. وقتی به درخت چند یال اضافه کنیم، طول مسیرها زیاد نمیشه و فقط میتونه کمتر بشه