إذا كان الرسم البياني G (V، E) متصل $ | E | \ GEQ | V | -1 $

Question

إذا كان الرسم البياني G (V، E) متصل عدد الحواف هو على الأقل عدد القمم -1. من الواضح جدا إذا كنت تفكر في ذلك ولكن كيف أثبت ذلك رسميا؟

Answer 1

تخيل عملية تبدأ به الرسم البياني الفارغ، وأضف الحواف واحدا تلو الآخر.تتبع عدد المكونات المتصلة.في البداية، هناك $ | الخامس | $ مكونات متصلة.كل حافة تضيف إما تنتمي داخل مكون متصل، أو يدمج مكونين متصلتين، وفي أي حال، ينخفض عدد المكونات المتصلة على الأكثر 1. وبالتالي بعد إضافة $ | الحواف، وعدد المكونات المتصلة هو على الأقل $ | الخامس |- | E | $ .إذا كان الرسم البياني متصل، $ |- | ه |\ leq 1 $ ، وكذلك $ | E |\ GEQ | الخامس |- 1 دولار .