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

[attachment=22300]

سلام
یال های gh,ij,kl,mn همگی یال برشی هستند(حذف انها باعث ناهمبند شدن یا به عبارتی افزایش تعداد مولفه ها می شود) پس این یال ها حتما در درخت فراگیر باید وجود داشته باشند.دو مثلت کناری هر کدام سه درخت فراگیر ایجاد می کنند در واقع با توجه به نکته تعداد درخت های فراگیر گراف [tex]K_n[/tex] برابر با [tex]n^{n-2}[/tex] و از طرفی سه لوزی (با قطر کوچک) داریم که هر کدام ۸ درخت فراگیر ایجاد می کنند یال وسط یا انتخاب می شود یا نمی شود اگر انتخاب نشود گراف [tex]c_4[/tex] را داریم که ۴ تا درخت فراگیر ایجاد می کند با توجه به اینکه گراف [tex]c_n[/tex] به تعداد n درخت فراگیر ایجاد می کند و اگر یال وسط انتخاب شود از بین دو یال بالا و پایین دو یال انتخاب می شود طوری که دور ایجاد نشود یعنی دو انتخاب در بالاو دو انتخاب در پایین که می شود ۴ انتخاب پس در کل [tex]3\times8\times8\times8\times3=4608[/tex] درخت فراگیر ایجاد می شود که در گزینه ها نیست