הוכחה:
$:(1)\implies(2)$ נתון כי $G$ הוא קשיר וחסר מעגלים ונדרש להוכיח שהוספת קשת תיצור מעגל פשוט.
יהיו $u,v \in V$. הגרף קשיר ולכן קיים מסלול פשוט מ-$u$ ל-$v$.
הוספת קשת $e$ שלא קיימת במעגל תצור מעגל פשוט.
$:(2)\implies(3)$ נתון כי $G$ הוא חסר מעגלים והוספת קשת תצור מעגל פשוט ונדרש להוכיח כי בין כל שני צמתים יש מסלול פשוט יחיד.
יהיו $u,v \in V$. נוסיף קשת בין $u,v$. לכן, נוצר מעגל פשוט. נסיר את הקשת שהוספנו ונקבל מסלול פשוט מ-$u$ ל-$v$.
נניח בשלילה שקיימים שני מסלולים פשוטים שונים:

אם $P$ הוא המשך של $P'$ אז נוצר לנו פה מעגל פשוט בסתירה לכך ש-$G$ חסר מעגלים.
אם יש פיצולים, אזי קיימים $j,r,s$ כך ש:

והצמתים $v_{j},v_{j+1},\dots,v_{r-1},v_{r}$ הינם שונים מ-$v_{j+1}',v_{j+2}',\dots,v_{s-1}'$.
קיבלנו מעגל פשוט:

בסתירה לכך שלא קיימים מעגלים. לכן, המסלול הפשוט יחיד!
$:(3)\implies(4)$ נתון כי בין כל שני צמתים ב-$G$ יש מסלול פשוט יחיד ונדרש להוכיח כי $G$ קשיר וכי הסרת כל קשת ממנו תפגום בקשירות.
בין כל שני צמתים יש מסלול פשוט ולכן, לפי הגדרה, $G$ קשיר.
נניח בשלילה כי קיימת קשת שהסרתה מהגרף אינה פוגמת בקשירות. אזי, יש יותר ממסלול פשוט אחד בין $u$ ל-$v$ בסתירה לכך שהמסלול הפשוט יחיד.
לכן, הסרת כל קשת מ-$G$ תפגום בקשירות.
$:(4)\implies (1)$ נתון כי $G$ קשיר, והסרת כל קשת ממנו תפגום בקשירות ונדרש להוכיח כי $G$ הוא עץ(קשיר וחסר מעגלים).
נתון כי $G$ קשיר ולכן, נדרש להוכיח כי $G$ חסר מעגלים.
נניח בשלילה כי יש מעגל פשוט. נוריד את אחת הקשתות ונקבל גרף $G'$.
יהיו $w,w' \in V$. הגרף קשיר ולכן קיים מסלול $P$ בין $w$ ל-$w'$ ב-$G$.
אם $P$ אינו כולל את הקשת שהורדנו, אז הוא גם מסלול ב-$G'$. אם $P$ כולל את הקשת שהורדנו, נחליפה במסלול אחר ונקבל מסלול ב-$G'$.
לכן, לפי הגדרה, הגרף קשיר וזוהי סתירה לכך שהסרת כל קשת ממנו תפגום בקשירות.
לכן, $G$ הינו עץ!
∎

כלומר, אנו לוקחים את כל הקשתות שבאות עם הצמתים שלקנו מהגרף כדי שהוא יהיה מושרה.

יחס הנגישות מחלק את קבוצת צמתי הגרף למחלקות קשירות, כך ששני צמתים נמצאים באותה מחלקה $\iff$ הם נגישים זה מזה.

הוכחה:
$:(1)\implies(2)$ נתון כי $G$ הוא עץ וצ"ל ש-$G$ חסר מעגלים ומתקיים $|E|=|V|-1$.
נתון כי $G$ הוא עץ ולכן הוא חסר מעגלים.
נוכיח באינדוקציה כי $|E|=|V|-1$.
בסיס: $|V|=n=1$ ואז $|E|=0=1-1$.
צעד: נניח כי עבור $|V|=n$ מתקיים $|E|=n-1$ ונוכיח כי עבור $|V|=n+1$ מתקיים $|E|=n$.
יש לפחות קשת אחת ולכן יש לפחות עלה אחד. נסיר אותו ואת הקשת אליה הוא מחובר.
נקבל עץ $T'=(V',E')$ עם $n$ צמתים. לפי הנחת האינדוקציה נקבל:

כנדרש.
$:(2)\implies(3)$ נתון כי $G$ הוא חסר מעגלים ו-$|E|=|V|-1$ וצ"ל כי $G$ קשיר ובנוסף $|E|=|V|-1$.
$G$ חסר מעגלים ולכן הוא יער. לפי המסקנה שתגיע לאחר ההוכחה, $|E|=|V|-(\R{\text{מספר רכיבי הקשירות}})$.
נתון כי $|E|=|V|-1$ ולכן מספר הרכיבים הקשירים הוא $1$ ולכן $G$ קשיר.
$:(3)\implies (1)$ זהה להוכחת המסקנה השנייה שתגיע לאחר ההוכחה.
∎

הוכחה:
כל רכיב קשיר $G_{i}=(V_{i},E_{i})$ הוא עץ.

∎

הוכחה:
אם $G$ קשיר והוא אינו עץ, נסיר קשתות כל עוד הקשירות אינה נפגמת.
לכן, ניתן להסיר קשת אחת לפחות בלי לפגום בקשירות.
הגרף האחרון שנקבל יהיה עץ $G'=(V,E')$ ולכן:

∎

סופרים עצים

נניח ויש לנו עץ בעל $n$ צמתים שונים.
נסמן ב-$\tau_{n}$ את מספר העצים על קבוצת הצמתים $\Sigma=\left\{ 1,2,3,\dots,n \right\}$.

הוכחה:
נגדיר באופן רקורסיבי התאמה $\phi$ בין קבוצת העצים על קבוצת הצמתים $\Sigma$ בגודל $n$ לבין קבוצת המילים $\Sigma^{n-2}$ ונוכיח כי היא חח"ע ועל.
נניח סדר על האיברים של $\Sigma$. למשל $1<2<\dots<n$.
אם העץ $T$ מכיל שני צמתים, אזי $\phi(T)$ היא המילה הריקה. אחרת:

• יהי $v$ עלה מינימלי ב-$T$.
• תהי $v\edge{e}u$ הקשת היחידה ב-$T$ המחוברת אל $v$.
• יהי $T'$ העץ על $\Sigma \setminus \left\{ v \right\}$ המתקבל מהסרת $v$ ו-$e$ מ-$T$.
• נגדיר $\phi(T)=u\phi(T')$.

תחילה נראה כי לכל עץ $T$ על קבוצת צמתים $\Sigma$ בגודל $n$, תמונת ההתאמה $\phi(T)$ היא מילה ב-$\Sigma^{n-2}$ באמצעות אינדוקציה:
בסיס: עבור $n=2$ מתקיים כי $\phi(v\edge{e}u)$ היא המילה הריקה שאורכה $0$.
צעד: נניח נכונות עבור $n-1\geq 2$ ונוכיח עבור $n\geq 3$.

כאשר $u \in\Sigma$ ו-$\phi (T')\in\Sigma^{n-3}$ ולכן $\phi \in\Sigma^{n-2}$.
לכן, לכל עץ $T$ מתקיים $\phi(T)\in\Sigma^{n-2}$.

נראה כעת כי הצומת $v$ הוא עלה ב-$v\iff T$ אינו מופיע ב-$\phi(T)$:
⟸: יהיו $T=T_{0},T_{1},\dots,T_{n-2}$ העצים המתקבלים במהלך החישוב $\phi(T)$.
הסרת צומת $+$ קשת, אינה מגדילה את דרגות שאר הצמתים ולכן, אם $v$ עלה ב-$T$ אזי הוא עלה ב-$T_{i}$ או אינו מופיע כלל ב-$T_{i}$. שכנו של עלה $v$ יכול להיות עלה רק בעץ האחרון $T_{n-2}$.
לכן, $v$ לא יופיע ב-$\phi(T)$.
⟹: אם $v$ אינו עלה ב-$T$, אזי דרגתו $2\leq$.
בשלב מסויים בחישוב $\phi(T)$ דרגתו תרד מ-$2$ ל-$1$. בשלב זה מסירים שכן שלו ולכן $v$ יופיע ב-$\phi(T)$.

לכן, הצומת $v$ הוא עלה ב-$v\iff T$ אינו מופיע ב-$\phi(T)$.

נגדיר באופן רקורסיבי התאמה $\theta$ בין קבוצת המילים $\Sigma^{n-2}$ כאשר $|\Sigma|=n$ לבין קבוצת העלים על קבוצת הצמתים $\Sigma$ ונוכיח כי $\theta(s)=\phi^{-1}(s)$.
עבור מילה $s=s_{1}s_{2}\dots s_{n-2}$ מעל אלפבית $\Sigma$ בגודל $n\geq 2$:
אם $\Sigma=\left\{ u,v \right\}$ ו-$s$ המילה הריקה, אזי העץ $\theta(s)$ הוא הקשת $u\edge{e}v$.
אחרת, עבור: $|\Sigma|\geq 3$ נגדיר $\sigma$ מינימלי ב-$\Sigma$ שאינו מופיע במילה $s$.
$\tilde{T}=\theta(s_{2}s_{3}\dots s_{n-2})$ גרף על קבוצת הצמתים $\Sigma \setminus \left\{ \sigma \right\}$ ו-$\theta(s)$ הוא הגרף $\Sigma$ המתקבל מהוספת הקשת $\sigma \edge{e}s_{1}$ אל $\tilde{T}$.

נראה באינדוקציה כי עבור כל $s \in\Sigma^{n-2}$, התמונה $\theta(s)$ היא עץ על קבוצת הצמתים $\Sigma$.
בסיס: עבור $n=2$ המילה $s$ היא המילה הריקה מעל $\Sigma=\left\{ u,v \right\}$ ו-$\theta(s)=u\edge{e}v$ הוא עץ על $\Sigma$.
צעד: $s$ מילה באורך $n-2$ ולכן קיים $\sigma \in\Sigma$ מינימלי, אשר אינו מופיע ב-$s$. מהנחת האינדוקציה $\tilde{T}$ הוא עץ על $\Sigma \setminus \left\{ \sigma \right\}$ ולכן $\theta(s_{1}s_{2}s_{3}\dots s_{n-2})$ הוא עץ על $\Sigma$.
לכן, לכל מילה $s$ מתקיים $\theta(s)$ הוא עץ.

נראה כעת כי לכל עץ $T$ על קבוצה של שני צמתים לפחות מתקיים $\theta(\phi(T))=T$. כלומר, $T \longmapsto \phi(T)$ היא התאמה חח"ע בתחום שהוא קבוצת העצים על $\Sigma$.
בסיס: עבור $n=2$ קיימים עץ אחד על $\Sigma=\left\{ u,v \right\}$ ומילה ריקה אחת על $\Sigma$.
צעד: בהינתן עץ $T$ נסמן $\phi(T)\equiv s=s_{1}s_{2}\dots s_{n-2}=s_{1}s'$ ואז $\phi(T')\equiv s'$ כאשר $u\equiv s_{1}$.
בחישוב $\theta(s)$ מתקיים $\sigma\equiv v$ כי $v$ עלה מינימלי ב-$T$ ולכן אינו מופיע ב-$s$.

לכן, $T \rightarrow \phi(T)$ היא התאמה חח"ע בתחום שהוא קבוצת העצים על $\Sigma$.

כעת נראה באינדוקציה כי לכל מילה $s \in\Sigma^{n-2}$ כאשר $|\Sigma|=n$ מתקיים $\phi(\theta(s))=s$. כלומר, $T \longmapsto\phi(T)$ היא התאמה על הטווח $\Sigma^{n-2}$.
בסיס: עבור $n=2$ קיימים מילה ריקה אחת ועץ אחד.
צעד: בהינתן מילה $s=s_{1}s_{2}\dots s_{n-2}=s_{1}\tilde{s}$ נסמן $T\equiv\theta(s)=\tilde{T}\cup \left\{ \sigma \edge{e}s_{1} \right\}$ כאשר $\tilde{T}=\theta(\tilde{s})$.
$\sigma$ הוא עלה ב-$T$ ולכן, שאר העלים של $T$ הם עלים של $\tilde{T}$ ו-$s_{1}$ אינו עלה ב-$T$.
מהנחת האינדוקציה $\phi(\tilde{T})=\tilde{s}$ ולכן, העלים של $\tilde{T}$ אינם מופיעם ב-$\tilde{s}$.
לכן, $\sigma$ הוא עלה מינימלי ב-$T$ ולכן:

לכן, $T \rightarrow \phi(T)$ היא התאמה על הטווח $\Sigma^{n-2}$.

לכן, מכיוון שקיימת העתקה חח"ע ועל בין קבוצת העצים על קבוצת הצמתים $\Sigma$ בגודל $n$ לבין קבוצת המילים $\Sigma^{n-2}$ אזי מתקיים $\tau_{n}=n^{n-2}$.
∎

הוכחה:
אם $v$ עלה הלמה נובעת מההוכחה שראינו.
אם $v$ אינו עלה אזי בכל הסרת שכן של $v$ בעת חישוב $\phi(T)$ אנו מוסיפים את $v$ אל $\phi(T)$ ודרגתו של $v$ קטנה ב-$1$.
זאת עד אשר דרגתו מגיעה ל-$1$ ואז $v$ הופך לעלה.
∎

עצים מכוונים

​
מכיוון שקיום שורש גורר שגרף התשתית הינו קשיר, ניתן לנסח הגדרה שקולה:

הוכחה: ברור.

הוכחה:
$:(1)\implies (2)$ נתון כי $G$ הוא עץ מכוון ונדרש להוכיח כי ל-$G$ יש שורש עם $d_{in}(r)=0$ ועבור כל צומת $u$ אחר $d_{in}(u)=1$.
נניח בשלילה כי $d_{in}(r)>0$, כלומר, קיימת קשת $v \xrightarrow{e}r$. כיוון ש-$r$ שורש, קיים מסלול מכוון $P$ מ-$r$ ל-$v$.
קיבלנו את המעגל המכוון $Pe$ ב-$G$.
לכן, גם קיים מעגל פשוט ב-$G$ ולכןף קיים מעגל פשוט בגרף התשתיות בסתירה לכך שגרף התשתית של $G$ חסר מעגלים.
נניח בשלילה כי $d_{in}(u)\neq 1$ ונחלק למקרים:

• אם $d_{in}(u)=0$ לא ייתכן מסלול מ-$r$ אל $u$ בסתירה לכך שב-$G$ יש שורש.
• עבור $d_{in}(u)\geq 2$ ואז קיימות קשתות $u_{1}\xrightarrow{e_{1}}u$ ו-$u_{2}\xrightarrow{e_{2}}u$.
  קיים מסלול מכוון $P_{1}$ מ-$r$ אל $u_{1}$ ומסלול מכוון $P_{2}$ מ-$r$ אל $u_{2}$. ⟸ קיבלנו שני מסלולים שונים ב-$G$ מ-$r$ אל $u$.
  אם מישהו מהמסלולים אינו פשוט אז הוא מכיל מעגל פשוט ולכן גם גרף התשתית יכיל אז מעגל פשוט בסתירה לכך שלא קיימים מעגלים פשוטים.
  אחרת, בגרף התשתית קיימים שני מסלולים פשוטים שונים מ-$r$ אל $u$ בסתירה לכך שגרף התשתית הוא עץ.

$:(2)\implies(1)$ נתון כי ל-$G$ יש שורש $r$ עם $d_{in}(r)=0$ ועבור כל צומת $u$ אחר $d_{in}(u)=1$ וצ"ל כי $G$ הוא עץ מכוון.
נניח בשלילה כי יש מעגל פשוט בגרף התשתית:

אם ב-$G$ כיוון הקשת הראשונה הוא $v_{0}\xrightarrow{e_{1}}v_{1}$ אזי $d_{in}(v_{2})=1$ וגם $d_{in}(v_{1})=1$ ולכן, קיים ב-$G$ המעגל המכוון $v_{0}\xrightarrow{e_{1}}v_{1}\xrightarrow{e_{2}}\cdots\xrightarrow{e_{\ell-1}}v_{\ell-1}\xrightarrow{e_{\ell}}v_{0}$ אחרת קיים מעגל בכיוון ההפוך.
מכך ש-$d_{in}(r)=0$ נובע כי $r$ אינו על המעגל, אך מהיותו שורש, קיים מסלול $P$ מ-$r$ אל המעגל.
הצומת הראשון $v_{i}$ של המעגל על $P$ מקיים $d_{in}(v_{i})\geq 2$ בסתירה לכך שלכל צומת $u\neq r$ מתקיים $d_{in}(u)=1$.
∎

הוכחה:
הכיוון $(1)\implies(2)$ מיידי.
$:(2)\implies(1)$ יהי $u\neq v$ צומת. מכך שדרגת הכניסה של כל צומת השונה מ-$v$ היא 1 נקבל כי $d_{in}(u)=1$.
נלך מ-$u$ "אחורה" (נגד כיוון הקשתות) כל עוד קיימת קשת נכנסת לצומת. נראה כי התהליך סופי והוא מסתיים בהכרח ב-$v$.
לולא היה מסתיים, כי אז מסופיות הגרף היו קיימים $i\neq j$ כך ש-$u_{i}=u_{j}$ אך אז בגרף התשתית היה מעגל פשוט בסתירה לכך שגרף התשתית של $G$ חסר מעגלים.
לכן התהליך מסתיים, וצומת הסיום חייב להיות $v$ כי רק לו יש דרגת כניסה $0$.
מכאן שיש מסלול מ-$v$ אל כל צומת ב-$G$ ולכן $v$ הוא שורש ב-$G$.
∎

עץ פורש

הוכחה:
יהי $G=(V,E)$.
נוכיח באמצעות אלגוריתם: כל עוד קיים בגרף מעגל, נמחק קשת אחת מהמעגל.

1. סיום התהליך: התהליך חייב להסתיים, כי הגרף סופי, ולכן מספר הקשתות סופי.
   בכל צעד מורידים קשת אחת ולכן נעצור לאחר $|E|$ צעדים לכל היותר.
2. הפלט בסוף התהליך: נוכיח כי הגרף המתקבל קשיר וחסר מעגלים ולכן הוא עץ לא מכוון לפי הגדרה.
   חסר מעגלים: מהגדרת התהליך, בגרף המתקבל בסיומו אין מעגלים.
   קשיר: לאורך כל צעדי התהליך השמורה הבאה מתקיימת: הגרף קשיר. זאת מפאת היות התהליך איטרטיבי.
   נוכיח זאת באמצעות אינדוקציה:
   בסיס: נתון כי הגרף ההתחלתי הינו קשיר.
   צעד: נניח כי כל הצעדים עד הצעד $k$ השאירו את הגרף קשיר.
   בצעד ה-$k+1$ אנו מורידים קשת ממעגל והורדת קשת ממגעל אינה פוגעת בקשירות: נניח כי מסלול בין שני צמתים בגרף עובר בקשת $u\edge{}v$ אותה הסרנו, נוכל להלחיף את הקשת בתת המסלול $v \edge{}\dots \edge{}u$ שנמצא על המעגל מצידו השני. לכן, אם לפני הסרת הקשת היה מסלול בין כל זוג צמתים בגרף, הדבר מתקיים גם לאחר הסרתה.
   ∎

רעיון ההוכחה: נגדיר לכל צומת $v$ את מרחקו $dist(v)$ מהשורש $r$. כלומר, $dist(v)$ הוא אורך המסלול הקצר ביותר מ-$r$ אל $v$.
לכל צומת $v\neq r$ נבחר קשת $u \xrightarrow{e}v$ המקיימת $dist(u)=dist(v)-1$ ואותה נצרף לעת הפורש $H$.

• מדוע קיימת קשת כזו לכל $v\neq r$?
• מדוע $r$ הוא שורש גם בגרף $H$?
• מדוע $H$ חסר מעגלים?

הוכחה: תרגיל באינדוקציה :)

מטריצת השכנויות ומטריצת ה-$in-degree$

על מנת להוכיח את המשפט נדרש להוכיח כמה למות.

הוכחה:
בעץ אין מעגלים עצמיים ולכן:

$G$ הוא עץ מכוון ולכן, לפי משפט, ל-$G$ יש שורש $r$ בו מתקיים $d_{in}(r)=0$ ולכל צומת $u$ אחרת $d_{in}(u)=1$ ולכן, $L_{uu}=1$ עבור $u\neq r$.
מכיוון ש-$d_{in}(r)=0$ אזי עמודה $r$ ב-$A$ היא עמודת אפסים.
כל עמודה $u\neq r$ ב-$A$ מכילה איבר אחד שונה מ-$0$ מחוץ לאלכסון ואיבר זה שווה ל-$1$ ולכן, עמודה $r$ ב-$L$ היא עמודת אפסים וכל עמודה $u\neq r$ ב-$L$ מכילה איבר אחד שונה מ-$0$ מחוץ לאלכסון ואיבר זה שווה ל-$1$.
החלפת שמות הצמתים $u \leftrightarrow u'$ גורמת להחלפת שורות $u \leftrightarrow u'$ וכן עמודות $u\leftrightarrow u'$ ב-$L$ ולכן ערך הדטרמיננטה אינו משתנה.
לכן, ניתן להניח כי צמתי הגרף הם בסדר טופולוגי עולה שכן לכל קשת $u\arrowedge{e}v$ מתקיים $u<v$.
המטריצה $L^{(r)}$ המתקבלת היא משולשת עליונה בה כל איברי האלכסון שווים ל-$1$. לפי משפט, הדטרמיננה של מטריצה משולשת הוא מכפלת איברי האלכסון שלה ולכן $|L^{(r)}|=1$.
∎

הוכחה:
אם יש מעגל עצמי בצומת $u\neq r$ אזי עמודה $u$ ב-$L$ היא עמודת אפסים ולכן $|L^{(r)}|=0$.
נניח מכאן ואילך כי אין מעגלים עצמיים.

כיוון ש-$G$ איננו עץ מכוון, לפי משפט, $G$ אינו חסר מעגלים ולכן גרף התשתיות מכיל מעגל פשוט.

אם ב-$G$ כיוון הקשת הראשונה הוא $v_{0}\arrowedge{e_{1}}v_{1}$ אזי:

ולכן קיים ב-$G$ המעגל המכוון:

אחרת, קיים מעגל בכיוון ההפוך.
$d_{in}(r)=0$ ולכן $r$ אינו על המעגל.
עבור כל צומת אחר $u$ מתקיים $d_{in}(u)=1$ ולכן אין קשתות נכנסות אל המעגל.

נשנה את שמות הצמתים $v_{i}\leftrightarrow i+1$. סכום $\ell$ העמודות הראשונות ב-$L$ הוא $0$. כלומר, עמודות אלו ת"ל והן ת"ל גם ב-$L^{(r)}$.
לכן, $|L^{(r)}|=0$.
∎

הוכחה למשפט קירכהוף:
נוכיח באינדוקציה על מספר הקשתות על מספר הקשתות $|E|$ עבור מספר צמתים $|V|$ נתון.
בסיס: $|E|\leq |V|-1$.
לפי משפט, $\sum_{v \in V}d_{in}(v)=|E|$ ולכן מתקיים אחד התנאים הבאים:

• קיים ב-$G$ צומת אחד לפחות $v \neq r$ כך ש-$d_{in}(v)=0$.
  במקרה זה, $v$ אינו נגיש מ-$r$ ולכן אין עצים פורשים ששורשם $r$.
  עמודה $v$ ב-$L$ הינה עמודת אפסים ולכן $\det(L^{(r)})=0$.
• $d_{in}(r)=0$ ועבור כל צומת $u$ אחר $d_{in}(u)=1$.
  נחלק למקרים:
  • אם $r$ הוא שורש, אזי, לפי משפט, $G$ הוא עץ מכוון עם שורש $r$ וככזה יש ב-$G$ עץ פורש אחד.
    לכן, לפי למה ממקודם, $\det(L^{(r)})=1$.
  • אם $r$ איננו שורש ב-$G$, בפרט אין עצים פורשים ששורשם $r$ ולכן, לפי משפט, $G$ איננו עץ מכוון ולכן, לפי למה ממקום, $\det(L^{(r)})=0$.

צעד: יהי $|E|\geq |V|$ ונניח נכונות המשפט עבור כל $|E'|< |E|$.
נניח כי ב-$G$ אין לולאות עצמיות, כיוון שעץ פורש לעולם לא יכיל אותם ו-$L$ אינו תלוי בהם.
לפי משפט, $\sum_{v \in V}d_{in}(v)=|E|$ ולכן מתקיים אחד התנאים הבאים:

• $d_{in}(r)>0$, כלומר, קיימת קשת אחת לפחות $e$ הנכנסת אל $r$.
  אף עץ פורש עם שורש $r$ לא יכיל את הקשת $e$.
  יהי $\tilde{G}=(V,\tilde{E})$ תת-הגרף של $G$ המתקבל מהסרת הקשת $e$.
  מספר העצים הפורשים עם שורש $r$ זהה ב-$G$ וב-$\tilde{G}$.
  $|\tilde{E}|<|E|$ ולכן חלה על $\tilde{G}$ הנחת האינדוקציה.
  המטריצות $\tilde{L},L$ שונות רק בעמודה $r$ ולכן $\tilde{L}^{(r)}=L^{(r)}$.
  $\det(L^{(r)})=\det(\tilde{L}^{(r)})\underset{\begin{matrix} \downarrow \\ \R{\text{הנחת האינדוקציה}} \end{matrix}}{=}\boxed{\begin{matrix} \R{\text{מספר העצים הפורשים}} \\ r\;\R{\text{עם שורש}}\; \tilde{G}\;\R{\text{של}} \end{matrix}}=\boxed{\begin{matrix} \R{\text{מספר העצים הפורשים}} \\ r\;\R{\text{עם שורש}}\; {G}\;\R{\text{של}} \end{matrix}}$
• קיים $v\neq r$ כך ש-$d_{in}(v)>1$.
  נבחר קשת מסוימת $e$ נכנסת אל $v$ ונגדיר גרפים $G_{0}$ ו-$G_{1}$.
  נסמן ב-$N_{1},N_{0},N$ את מספר העצים המכוונים הפורשים של הגרפים $G_{1},G_{0},G$ עם שורש $r$.
  ניתן לחלק את קבוצת העצים הפורשים של $G$ עם שורש $r$ לשתי תת קבוצות זרות:
  • הקשת $e$ איננה בעץ הפורש.
  • הקשת $e$ שייכת לעץ הפורש, ואז העץ הפורש אינו מכיל אף קשת אחרת הנכנסת אל $v$.
    לכן מתקיים $\det(L^{(r)})=drt(L_{0}^{(r)})+\det(L_{1}^{(r)})$ ולכן, מהנחת האינדוקציה:
    $\det(L^{(r)})=\det(L_{0}^{(r)})+\det(L_{1}^{(r_{1})})=N_{0}+N_{1}=N$

ולכן, מספר העצים הפורשים עם שורש $r$ בגרף מכוון $G$ הינו $\det(L^{(r)})$.
∎

עץ פורש בגרף לא מכוון

מטריצת השכנויות מוגדרת זהה לממקודם רק שפה היא בהכרח תהיה סימטרית שכן יש רק $d$ ולא $d_{in},d_{out}$.

הוכחה:
נבנה גרף מכוון $\vec{G}=(V,\vec{E})$ ע"י החלפת כל קשת ב-$G$ לזוג קשתות אנטי-מקבילות.
מתקיים כי $\vec{A}=A,\vec{\Delta}=\Delta,\vec{L}=L$ ולכן לכל $r \in V$ מתקיים:

עבור כל עץ פורש $\vec{H}$ של $\vec{G}$ עם שורש $r$, גרף התשתיות שלו הוא עץ פורש $H$ של $G$.
ההתאמה $\vec{H}\to H$ היא הפיכה, כלומר, חח"ע ועל (תרגיל) ולכן, לפי משפט קירהכוף מתקיים כי מספר העצים הפורשים ב-$\vec{G}$ המתחילים ב-$r$ הינו $\det(L^{(r)})$.
לכן, מספר העצים הפורשים בגרף לא מכוון $G=(V,E)$ הינו $\det(L^{(r)})$ לכל $r \in V$.
∎