הוכח שמספר עצים מכוונים הפורשים n צמתים שונים הוא n^{n-1}:
- באמצעות שימוש במשפט קירכהוף.
- באמצעות שימוש במשפט קיילי לעצים לא מכוונים.
סעיף א
מטריצת דרגות הכניסה M המתאימה לגרף המלא הינה:
M=\begin{bmatrix}n-1 & -1 & -1 & \ldots & -1\\
-1 & n-1 & -1 & \ldots & -1\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
-1 & -1 & -1 & \ldots & -1\\
-1 & -1 & -1 & \ldots & n-1
\end{bmatrix}
נשים לב כי הדטרמיננטה של המטריצה M שווה ל-n^{n-2}. כל דטרמיננטה כזאת מתאימה לבחירת צומת אחר כשורש. לכן התשובה הינה:
n\cdot n^{n-2}=n^{n-1}
סעיף ב
ע"פ משפט קיילי מספר העצים הלא מכוונים הוא n^{n-2}. כדי לכוון את הגרף נבחר שורש ב-n אפשרויות. סה"כ ע"פ עקרון הכפל נקבל:
n\cdot n^{n-2}=n^{n-1}