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

נתון גרף לא-מכוון וקשיר $\displaystyle G=(V,E)$, וכן טבלת עלויות על הקשתות Edge-Costs. ידוע שקיימת קשת $\displaystyle e\in E$ כלשהי כך שEdge-Costs[e] < Edge-Costs[e'] לכל קשת $\displaystyle E\ni e'\neq e$. במילים אחרות, $\displaystyle e$ היא הקשת הזולה ביותר (ממש).

אנא הוכח או הפרך את הטענה הבאה. הקשת $\displaystyle e$ שייכת לכל עפ"מ של $\displaystyle G$.

שימו לב: משפט הקשת הקלה - קשת בטוחה מוכיח לכשלעצמו רק שקיים עפ"מ המכיל את $\displaystyle e$. השאלה מתייחסת לטענה חזקה יותר מכך.