گراف همبند

{connected graph} [ریاضی] گرافی که بین هر دو زوج از رأس های متمایز آن مسیری موجود باشد

گرافی که بین هر دو زوج از رأس‌های متمایز آن مسیری موجود باشد.

💡 الگوریتم حذف معکوس این تضمین را می‌دهد که گراف همبند باقی بماند، چون تنها در صورتی یالی را حذف می‌کند که باعث ناهمبند شدن گراف نشود. هر یالی که حذف می‌شود قبل از حذف در دوری شرکت داشته‌است. از آنجایی که الگوریتم از یال با بیشترین وزن شروع به حذف کردن می‌کند، آن یال بزرگ‌ترین یال در دور مربوط به خود است. پس بنابر تعریف درخت پوشای کمینه، یال حذف شده جزء درخت پوشای کمینه نخواهد بود.