گرافی ۱۰۰۰ رأسی با رأس‌های ۱ تا ۱۰۰۰ در نظر بگیرید. برای هر $1 \le i < j \le 1000$، بین دو رأس $i$ و $j$ یال قرار می‌دهیم، اگر و تنها اگر $i$ اُمین رقم نمایش دودویی عدد $j$ (از سمت راست) برابر ۱ باشد. کوچک‌ترین $k$ را بیابید که بتوان با $k$ رنگ رأس‌های این گراف را رنگ‌آمیزی کرد، طوری که هر دو رأس مجاور ناهم‌رنگ باشند.
پاسخ
گزینه‌ی ۳ درست است.
ابتدا ثابت می‌کنیم رنگ‌آمیزی با کم‌تر از چهار رنگ امکان ندارد. رأس‌های شماره ۱، ۳، ۵ و ۲۱ دوبه‌دو به هم وصل هستند. پس دست کم به ۴ رنگ نیاز داریم. حال نشان می‌دهیم چهار رنگ برای رنگ‌آمیزی کافی است. رأس‌های ۱ و ۲ را با رنگ $A$، رأس ۳ را با رنگ $B$، رأس‌های ۴ تا ۱۵ را با رنگ $C$ و رأس‌های ۱۶ تا ۱۰۰۰ را با رنگ $D$ رنگ کنید.