سوال مورد نظر پیوست شده است
ممنون از دوستان
#رنگ آمیزی گراف پترسن
سلام. وقت بخیر.
اگه به یه راس یه رنگ بدید، اون رنگ رو نمیشه برای همسایههای همسایههای اون گره استفاده کرد. یعنی هیچ گرهی که فاصلش کمتر از ۳ باشه با گرهی که رنگ ۱ داره، نمیتونه رنگ ۱ بگیره. با توجه به اینکه حداکثر فاصله از یک گره تا سایر گره ها در این گراف برابر ۲ هست، هیچ رنگی نمیتونه برای دو گره استفاده بشه. پس ۱۰ رنگ نیازه.