מפעילים את אלגוריתם כיווץ הקשתות שהוצג בהרצאה על גרף G=(V,E) בעל n קודקודים, עד שנותרים בגרף 2 קודקודים. יהא (…

מפעילים את אלגוריתם כיווץ הקשתות שהוצג בהרצאה על גרף $G=(V,E)$ בעל $n$ קודקודים, עד שנותרים בגרף $2\le\ell$ קודקודים. יהא $(S,\bar S)$ חתך מינימלי בגרף $G$. הוכיחו כי ההסתברות לכך שאף קשת החוצה חתך זה לא כווצה במהלך ריצת האלגוריתם היא לפחות

$$\frac{\binom{\ell}{2}}{\binom{n}{2}}.$$