گراف همبند و بی‌وزن ‎$G$‎ را در نظر بگیرید. ‎$G$‎ را ‎$k$‎-زیبا گوییم اگر بتوان یال‌های آن را اعداد با ‎۱‎ تا ‎$k$‎ طوری وزن‌دار کرد که کم‌وزن‌ترین مسیر بین هر دو راس یکتا باشد (وزن یک مسیر جمع اعداد روی یال‌های آن است). ‎$k(G)$‎ را کمترین ‎$k$‎ می‌گیریم که $G$، ‎ ‎$k$‎-زیبا باشد. اندازه (تعداد رئوس) بزرگ‌ترین مولفه دوهمبند راسی ‎$G$‎ را ‎$c(G)$‎ بگیرید.

ثابت کنید به ازای هر گراف همبند $G$، ‎ ‎ ‎$k(G)<c(G)$‎ است.

• سوال بعد
• سوال قبل