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

נניח שנוסיף לגרף את הקשת $(u, v)$ . להלן העץ לפני הוספת הקשת.

נזכור שעץ הוא קשיר עפ"י ההגדרה, ולכן לפני הוספת הקשת, היה מסלול $P$ מ $u$ ל $v$ .

לכן, לאחר הוספת הקשת $(u, v),$ יש מסלול מ $u$ לעצמו: המסלול $P$ שאליו משורשרת הקשת $(u, v)$ .