Problema 10

Considerăm un graf neorientat complet cu nodurile $\{1,2,\dots,10\}$. Alegem exact $9$ muchii astfel încât subgraful format are următoarele proprietăți: (1) este conex; (2) nu conține niciun ciclu; și (3) nodurile $1$, $2$, $3$ și $4$ au gradul $1$ în subgraful format. Câte astfel de alegeri distincte putem face pentru ca subgraful rezultat să îndeplinească toate cele trei condiții?

a) $6^8$; b) $4!\cdot 6^4$; c) $10^8$; d) $7^8$; e) $10\cdot 6^7$; f) $6^7$.