کمترین تعداد رنگ برای رنگ‌آمیزی استان‌های ایران، ۴ رنگ است.

پاسخ‌سوال‌های تکمیلی: ۲۸ استان را می‌توان با ۳ رنگ رنگ‌آمیزی کرد. ۲۱ استان را می‌توان ۲ رنگ رنگ‌آمیزی کرد. ۱۲ استان را می‌توان با یک رنگ رنگ‌آمیزی کرد.

نقشه شهرهای ایران یه گراف با ۳۱ راس و یال های زیر تولید می‌کند:

[(0, 2), (0, 7), (0, 11), (1, 2), (1, 3), (1, 7), (2, 7), (3, 7), (3, 9), (3, 10), (4, 5), (4, 6), (4, 8), (5, 8), (5, 9), (6, 8), (6, 18), (7, 10), (7, 11), (7, 14), (8, 9), (8, 13), (8, 17), (8, 18), (8, 20), (9, 10), (9, 12), (9, 13), (10, 12), (10, 14), (10, 15), (11, 14), (11, 16), (12, 13), (12, 15), (13, 15), (13, 17), (14, 15), (14, 16), (14, 19), (15, 17), (15, 19), (15, 20), (16, 19), (16, 21), (17, 20), (18, 20), (18, 22), (18, 25), (18, 27), (19, 20), (19, 21), (19, 23), (19, 24), (20, 22), (20, 24), (20, 26), (20, 28), (21, 23), (22, 25), (22, 26), (23, 24), (23, 28), (23, 29), (24, 28), (25, 26), (25, 27), (25, 30), (26, 28), (26, 29), (26, 30), (27, 30), (28, 29), (29, 30)]

تعداد رنگ آمیزی های با ۴ رنگ برابر است با 12427583.

یک نمونه در زیر آمده است:

با کمتر از ۴ رنگ نمی‌شود رنگ کرد، زیرا بعضی استان‌ها (مثل اصفهان) تعداد فرد تا همسایه دارن که زنجیره وار با هم همسایه‌اند و برای رنگ کردن این همسایه‌ها حداقل ۳ رنگ لازم است، و رنگ استان وسط باید با این ۳ رنگ متفاوت باشد.

پاسخ سوال‌های تکمیلی:

می‌توان ۲۸ استان از ۳۱ استان را به ۳ رنگ رنگ کرد بطوری که هیچ استان مجاوری همرنگ نباشد:

میتوان ۲۱ استان از ۳۱ استان را با ۲ رنگ رنگ کرد بطوری که هیچ استان مجاوری همرنگ نباشد:

میتوان ۱۲ استان از ۳۱ استان را با تنها یک رنگ رنگ کرد بطوری که هیچ استان مجاوری همرنگ نباشد (در واقع این بزرگترین زیرمجموعه از استان‌هاست که هیچ عضوی از آن همسایه نیست):