پیکاسو نقاش مطرح سبک کوبیسم بود که توانایی نقاشی و رنگآمیزی هرچیزی را داشت. او برای رنگآمیزی درختها از دو اصل عدم شلختگی و مهم{عدم کسلکنندگی} پیروی میکرد:
چند درخت ده رأسی وجود دارد که پیکاسو آنها را با توجه به اصول رنگآمیزی خود با دقیقاً چهار رنگ مختلف رنگآمیزی میکند؟ دو درخت $T_1$ و $T_2$ متفاوت هستند، اگر و تنها اگر یالی مانند $(u, v)$ در درخت $T_1$ بین دو رأس $u$ و $v$ وجود داشته باشد که در درخت $T_2$ قرار نداشته باشد.
پاسخ
گزینهی ۵ درست است.
اگر درختی یک مسیر با $k$ رأس داشته باشد، نقاش حداقل از $k$ رنگ برای رنگآمیزی آن استفاده میکند. از طرفی تنها درخت $n$ رأسی که مسیر ۴ رأسی ندارد، گراف $S_n$ (ستارهی $n$ رأسی) است که نقاش آن را با ۳ رنگ، رنگآمیزی میکند. این نشان میدهد که درختهای $n$ رأسیای که پیکاسو آنها را با ۴ رنگ، رنگآمیزی میکند، مسیری با ۴ رأس مانند $\langle p_1-p_2-p_3-p_4 \rangle$ دارند. از طرفی $ p_1$ و $ p_4$ رأس مجاور دیگری ندارند؛ در غیر این صورت بلندترین مسیر گراف بزرگتر از ۴ خواهد شد. با استدلال مشابهی میتوان گفت که سایر رأسها دقیقاً به یکی از $p_2$ و $p_3$ متصل هستند.
در انتها دقت کنید از آنجا که رأسهای مجاور $p_2$ و $ p_3$ حداکثر دو رنگ متفاوت دارند و هر رأسی دقیقاً مجاور یکی از این دو است، گرافی که شرایط فوق را داشته باشد با حداکثر ۴ رنگ، رنگآمیزی میشود. مطابق استدلالهای فوق، به $\binom{10}{2} = 45$ طریق رأسهای $p_2$ و $p_3$ را انتخاب میکنیم و رأس مجاور ۸ رأس باقیمانده را به $2^8 - 2 = 254$ طریق انتخاب میکنیم. در انتها حاصل برابر با $45 \times 254 = 11430$ میشود.