برای گراف بدون جهت این طور باید تحلیل کرد که اگرتعداد یالهای ما برای یک گراف n راسی برابربا تعدادیالهای گراف کامل n-1 راسی به اضافه ی یک یال باشد حتما گراف ما همبنداست.برای گراف جهتدار اگرگراف با حذف جهت ها همبند باشد، گراف ما همبند است.

سلام

نکته ۱ : یک گراف ساده n راسی اگر کمتر از (n-1) یال داشته باشد، حتما ناهمبند است (همبند نیست)
نکته ۲ : یک گراف n راسی اگر بیشتر از [tex]\binom{n-1}{2}[/tex] یال داشته باشد، حتما همبند می باشد، در غیر اینصورت ممکن است همبند یا ناهمبند باشد.

موفق باشید