Apakah ada dua pohon rentang dari grafik sederhana selalu memiliki beberapa tepi yang sama?

Saya mencoba beberapa kasus dan menemukan dua pohon spanning dari grafik sederhana memiliki beberapa tepi yang sama. Maksudku, aku tidak bisa menemukan contoh balasan sejauh ini. Tapi aku juga tidak bisa membuktikan atau membantahnya. Bagaimana cara membuktikan atau menyangkal dugaan ini?

Tidak, perhatikan grafik lengkap $K_4$ :

Ini memiliki pohon merentang ujung-disjoint berikut:

Untuk pembaca yang lebih tertarik, ada beberapa penelitian tentang dekomposisi grafik menjadi pohon span-disjoint edge .

Sebagai contoh, makalah-makalah klasik tentang Masalah Menguraikan Grafik menjadi $n$ Faktor-Faktor yang Dihubungkan oleh WT Tutte dan Edge-disjoint spanning tree dari graf berhingga oleh C. St.JA Nash-Williams memberikan karakterisasi grafik yang mengandung $k$ berpasangan edge-disjoint merentang pohon.

$K_{4k+2}$${2k+1}$

$K_{2n}$

Anda dapat mencari lebih banyak. Misalnya, pencarian Google untuk dekomposisi grafik menjadi spanning tree .

$K_4$

Tidak, itu tidak benar bahwa dua pohon rentang dari grafik memiliki tepi yang sama.

Pertimbangkan grafik roda:

Anda dapat membuat spanning tree dengan tepi "di dalam" loop dan satu lagi dari loop luar.

$K_n$$n\geq4$

$2$

$K_n$$n\geq4$$n\geq4$$2$

$2$

1. $2$$2$
2. Apakah ada grafik selain roda atau roda sebagai subgrafnya yang merentang pohon dengan ujung yang terputus-putus?

$K_{2k}$

$0\leq i < k$

$n$$n+1$

Jika grafik memiliki jembatan (yaitu tepi yang penghapusannya memutus grafik), maka tepi ini harus dimiliki oleh setiap pohon rentang. Secara intuitif, jembatan adalah satu-satunya tepi yang menghubungkan dua titik akhir dan karenanya harus dimiliki oleh setiap subgraf yang terhubung.

Di sisi lain, jika tepi grafik termasuk dalam siklus, maka ada pohon spanning yang tidak mengandung tepi ini.

Jadi, jika setiap tepi grafik milik siklus, maka tidak ada tepi yang umum untuk semua pohon spanning (yaitu, persimpangan set tepi pohon spanning adalah set kosong).