گراف بدون جهت $G$، k-خوشحال است اگر و تنها اگر بتوان رئوس آن را با اعداد از ۱ تا $k$ طوری برچسب‌گذاری کرد به طوری‌که برای هر دو راس متمایز $u$ و $v$‌که برچسب یکسان $x$‌ دارند، در هر مسیر از $u$ به $v$ راسی با برچسب بیش‌تر از $x$ وجود داشته باشد.

مثلا گراف شکل زیر ۳-خوشحال است.

عدد خوشحالی یک گراف، کم‌ترین $k$ ای است که گراف $G$، k-خوشحال باشد. مثلا عدد خوشحالی گراف شکل بالا، ۳ است. عدد خوشحالی مسیر n-راسی را به‌دست آورده، ادعای خود را ثابت کنید.

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