אם היא קבוצת ההיזון החוזר הזולה ביותר, אז היא קבוצת קשתות עץ פורש מקסימום.
נסמן כ את מחיר כל קשת (כלומר Edge-Costs[e]), ונסמן כאת סך משקל הקשתות, .
הוכחה: הקבוצה , היא, עפ"י ההגדרה, הקבוצה המביאה למינימום את
כך שחסרת מעגלים. במילים אחרות, הקבוצה היא הקבוצה כך שהקבוצה היא הקבוצה היקרה ביותר שעדיין חסרת מעגלים, ולכן היא היער היקר ביותר. אבל קל לראות שאם איננה עץ, אז יש קבוצה חסרת מעגלים יקרה לפחות כמוה (הגרף קשיר, ולכן תהיה לפחות עוד קשת אחת המחברת שני עצים ממנה).
נמצא, לכן, דרך יעילה למצוא עץ פורש מקסימום בגרף.
נסמן כ את מחיר הקשת היקרה ביותר פלוס 1 (כלומר ), ונסמן לכל קשת , .
משפט:
אם נבנה טבלה Edge-Costs'כל שלכל קשת , Edge-Costs'[e], ונריץ אלגוריתם עץ פורש מינימום עם Edge-Costs', אז קבוצת הקשתות שתוחזר תהווה קשתות לעץ פורש מקסימום עם Edge-Costs.
הוכחה: נשים לב שכל חיובי ממש (לפי הבניה), ולכן נוכל להריץ אלגוריתם עץ פורש מינימום עם Edge-Costs', והקבוצה שתוחזר לנו תהיה קבוצה בת גודל . בנוסף,
![{\displaystyle \displaystyle \sum _{e\in E}[w_{e}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4df2a4b96b7532dc5741a9a04a6b34b8e7c2ebba)
![{\displaystyle \displaystyle \sum _{e\in E'}[w_{e}]=w-\sum _{e\in E\setminus E'}[w_{e}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1a2af1ac78f4e548ea076bdbd09dfede706344e)
![{\displaystyle \displaystyle {\bar {u}}=\max _{e\in E}[w_{e}]+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18a86563b8081dd5bcadfd5a1ad7b2804b173d62)
![{\displaystyle \displaystyle \min _{W}\sum _{e\in W}[w'_{e}]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ea86901e244e4357eca721039f51adef232b73c)
![{\displaystyle \displaystyle \min _{W}\sum _{e\in W}[{\bar {u}}-w_{e}]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/384d8a8693697e13e2da0777797f19caa0b41c62)
![{\displaystyle \displaystyle \min _{W}[(|V|-1)\cdot {\bar {u}}-\sum _{e\in W}[w_{e}]]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d51bb2226b2d6f43afe691beb4463b6fc578963d)
![{\displaystyle \displaystyle (|V|-1)\cdot {\bar {u}}-\max _{W}\sum _{e\in W}[w_{e}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec744f4be9248bcbe72dc43eacbf9f8079e5116a)
