Berapa banyak pohon $e$ tepi dalam klik berlabel

Question

Diberikan klik berlabel $G=(E,V)$, Saya ingin menghitung jumlah pohon yang dapat dibuat untuk sejumlah tepi $e$, sehingga semua node di pohon terhubung.

Misalnya, biarkan $G$menjadi grafik 4-klik. Saya ingin mencari jumlah pohon dengan 3 tepi yang dapat dibentuk sebagai subgraf.

Saya telah mencoba untuk meneliti ini, tetapi tidak dapat benar-benar memahami literatur. Posting MSE ini terlihat sangat mirip dengan pertanyaan saya, tetapi saya kesulitan dengan jawabannya.

Inilah upaya saya untuk mengatasi masalah ini. Pertama-tama kami menghitung jumlah total cara memilih 3 tepi dari 4-klik. Ada total 6 tepi. Ada$6\cdot 5 \cdot 4 = 120 $berbagai cara untuk membuat pilihan; namun, banyak di antaranya yang setara satu sama lain. Faktanya, dengan tiga pilihan edge,$\{e_1,e_2,e_3\}$, urutan pengambilannya tidak masalah. Jadi kita harus membagi 120 dengan jumlah permutasi kata 3 huruf, yaitu 6. Oleh karena itu, jumlah grafik yang dapat dibuat dari pilihan 3 tepi dari 4-klik adalah$120/6= 20$ yang juga merupakan koefisien binomial

$$ \binom{6}{3} $$

Jumlah pohon tentunya harus kurang dari jumlah ini. Pendekatan naif saya adalah berpikir bahwa pohon berukuran 3 akan selalu berisi 4 node. Penelitian telah menunjukkan bahwa ada 16 pohon dalam kasus 4 klik dengan menggunakan$$ n^{n-2}=4^2=16 $$Namun, metode ini hanya berlaku dalam kasus ini. Untuk klik yang lebih besar, bagaimana saya bisa menemukan jumlah pohon dengan$e$ tepi, dimana $e\neq n-1$?

Kasus khusus $e=3$ adalah tujuan utama saya untuk sewenang-wenang $n$.

Answer 1

Pohon dengan $e$ tepi memiliki $e+1$node. Diberikan satu set$n$ node, ada $\binom n{e+1}$ cara untuk memilih himpunan node untuk pohon, dan kemudian dengan rumus Cayley ada $(e+1)^{e-1}$ pohon pada kumpulan node itu, jadi jawaban akhirnya adalah $$\binom n{e+1}(e+1)^{e-1}.$$