הוכחה:
לפי משפט, קיים ל-$G$ עץ פורש $T$.
ב-$G \setminus T$ יש בדיוק $|E|-|V|+1$ קשתות (הקשתות שהסרנו באלגוריתם). נסמנן $e_{1},e_{2},\dots,e_{|E|-|V|+1}$.
בגרף $T \cup \left\{ e_{i} \right\}$ קיים מעגל אשר נסמנו $C_{i}$ כי עץ הוא חסר מעגלים מקסימלי(לפי משפט).
$C_{i}$ בהכרח מכיל את $e_{i}$ כי אחרת, המעגל מוכל ב-$T$ בסתירה לכך שהוא עץ.
בסך הכל קיבלנו $|E|-|V|+1$ מעגלים $C_{1},C_{2},\dots,C_{|E|-|V|+1}$ בכל מעגל $C_{i}$ הקשת היחידה בו היא $e_{i}$.
∎

נסמן את דרגתו המקסימלית של צומת בעץ באמצעות $d$. בעץ יש $n-1$ קשתות ולכן סכום הדרגות של כל הצמתים הוא $2n-2$.

• ישנם $k$ צמתים בעלי דרגה $1$.
• ישנם $n-k-1$ צמתים בעלי דרגה $2$.
• ישנו צומת אחד בעל דרגה $d$.

לכן, $d=k$.
נאפיין את קבוצת המילים המתאימות לעצים הנ"ל לפי התאמה של משפט קיילי. נזכר כי מספר ההופעות של צומת במילה קטן ב-$1$ מדרגה שלו בעץ. לכן, $k$ צמתים לא מופיעים כלל במילה. $n-k-1$ צמתים מופיעים פעם אחת כל אחד וצומת אחד מופיע $k-1$ פעמים.

• מספר האפשרויות לבחור צומת בעל דרגה $k$ הוא $\begin{pmatrix}n \\ 1\end{pmatrix}$.
• מספר האפשרויות לבחור משאר הצמתים צמתים בעלי דרגה $2$ הוא $\begin{pmatrix}n-1 \\ n-k-1\end{pmatrix}$.
• מספר מילים באורך $n-2$ עם $k-1$ אותיות זהות וכל שאר האותיות שונות הוא $\frac{(n-2)!}{(k-1)!}$.

לכן, סה"כ נקבל:

נפתור מטעמי סימטריה.
יהי $G=(V,E)$ הגרף הלא מכוון המלא עם $n$ צמתים. נזכיר כי $|E|=\begin{pmatrix}n \\ 2\end{pmatrix}$.
לכל $e \in E$ נסמן ב-$T_{e}$ את מספר העצים הפורשים עם הקשת $e$. מטעמי סימטריצה לכל $T_{e}=T_{(1,2)}$.
לכן מתקיים:

נחשב את אגף שמאל בדרך אחרת:
טענה: $\displaystyle \sum_{e \in E}T_{e}=(n-1)n^{n-2}$.
הוכחה:
יהי $T=(V,E')$ עץ פורש על $n$ צמתים. לכל קשת $e \in E'$ העץ $T$ הוא עץ פורש המכיל את הקשת $e$ ולכן תורם $1$ ל-$T_{e}$.
כיוון ש-$|E'|=n-1$ הרי ש-$T$ תורם $n-1$ לסכום $\displaystyle \sum_{e \in E}T_{e}$. כיוון שהדבר נכון לכל עץ פורש, וכיוון שמספר העצים הפורשים הוא, לפי משפט קיילי, $n^{n-2}$ הרי שהטענה נכונה.

מטענה זו והמשוואה ממקודם נקבל ש:

בשיטת המשלים: לפי משפט קיילי יש $n^{n-2}$ עצים הפורשים $n$ צמתים ולכן מספר העצים שבהם הקשת $(1,2)$ לא מופיעה הוא:

∎

למת המתווך

​

הוכחה:
נניח בשלילה כי ב-$G$ אין שורש.
נגדיר לכל צומת $v$ בגרף $G$ את $k(v)$ - מספר הצמתים בגרף שקיים מסלול אליהם מ-$v$.
נסמן ע"י $a$ את הצומת עם מספר $k(a)$ הגבוה ביותר בגרף.
מתוך ההנחה קיים צומת $v$ כך שאין מסלול מ-$a$ ל-$v$.
יהיה $b$ המתווך של $a,v$. אזי, קיימים מסלולים מ-$b$ ל-$a$ ומ-$b$ ל-$v$ ולכן $k(a)<k(b)$ בסתירה למקסימליות של $k(a)$.
לכן, לפי הגדרה, $a$ הוא שורש(קיים מסלול מכוון ממנו לכל צומת בגרף)
∎