گراف ‎$G$‎ یک دورِ ‎$n$‎-رأسی می‌باشد. گراف ‎$H$‎ را از روی ‎$G$‎ به این صورت می‌سازیم که به ازای هر مسیر‎ (دقّ‎ت کنید که در گراف ‎$G$‎ بین هر دو رأس متفاوت ‎$i$‎ و ‎$j$‎ دقیقاً ‎$2$‎ مسیر وجود دارد) در ‎$G$‎ که ابتدا و انتهای آن متفاوند، یک رأس در ‎$H$‎ قرار می‌دهیم. سپس بین هر دو رأس از ‎$H$‎ یک یال قرار می‌دهیم اگر و فقط اگر مسیرهای متناظر این دو رأس در گراف ‎$G$‎ حداقل در یک یال اشتراک داشته باشند.

عدد رنگی گراف ‎$H$‎ چند است؟ ادعای خود را اثبات کنید.

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