پرسش

آیا رابطه ای بین یالها و راسهای یك گراف وجود دارد كه همبند و یا ناهمبند
بودن گراف را نشان دهد؟(با توضیح!)

پاسخ

می دانیم كه اگر از یك درخت هر یالی را حذف كنید ناهمبند می شود پس اگر یك گراف با n راس كمتر از n-1 یال داشته باشد حتما ناهمبند خواهد بود.
در ضمن یك گراف با n راس را طوری در نظر بگیرید كه شامل یك گراف كامل با n-1 است و یك راس تنها .هر یالی به این گراف اضافه شود گراف همبند خواهد بود پس اگر یك گراف با n راس شامل بیش از انتخاب 2 از n-1 یال باشد حتما همبند خواهد بود.