رنگ‌آمیزی نو با $k$ رنگ، رنگ‌آمیزیی است که هر یال را به‌یکی از اعداد $1$ تا $k$ نسبت می‌دهد. در یک رنگ‌آمیزی نو، حذف تمامی یالهای هر رنگ $i$ ($i \in \{1, 2, \ldots k\}$) گراف باقیمانده را همبند نگه می‌دارد. توجه کنید که این رنگ‌آمیزی تنها برای گراف‌هایی قابل انجام است که همبنداند و یال برشی ندارند. کم‌ترین تعداد رنگ لازم برای رنگ‌آمیزی نوِ هر گراف $n$ رأسی بدون یال برشی چقدر است؟ برای گفتهٔ خود دلیل بیاورید.