מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ/תרגילים/שימוש בקשת הזולה ביותר בגרף/תשובה

נניח שהטענה אינה נכונה, ו$\displaystyle e$ אינה חלק מקשתות העפ"מ. נניח ש$\displaystyle e$ יוצאת מצומת $\displaystyle x$ כלשהו. כפי שציינו בעבר, נוכל לצייר את העפ"מ כך ש$\displaystyle x$ הוא השורש שלו. הציור הבא מראה זאת. ילדי $\displaystyle x$ הם העצים $\displaystyle U_{1},...,U_{i}$.‏ $\displaystyle e$, שאיננה חלק מהעפ"מ, ולכן מצויירת בקו מקווקוו, יוצאת מ$\displaystyle x$ ומגיעה לצומת כלשהו ב$\displaystyle U_{j}$.

שימוש בקשת הקלה ביותר בגרף.

אך, כפי שהתרשים מראה, זה בלתי אפשרי. היות שכל קשת יקרה מ$\displaystyle e$, אז גם הקשת המחברת בין $\displaystyle x$ ל$\displaystyle U_{i}$ יקרה מ$\displaystyle e$. אפשר לראות בנקל שהחלפת שתי הקשתות תיצור עץ זול יותר מהעפ"מ (מה שכמובן בלתי אפשרי).