====== رنگ‌آمیزی طلایی ======


یال‌های گراف دوبخشی $G$‌را که هر بخش آن $n$‌راس دارد، با $2n-1$ رنگ، رنگ‌آمیزی کرده‌ایم. راس‌های بخش اول را با $x_1$ تا $x_n$ و راس‌های بخش دوم را با $y_1$ تا $y_n$ نام‌گذاری می‌کنیم. می‌دانیم که به ازای هر رنگ $(1\leq j \leq 2n-1)j$، و هر $(1\leq i \leq n)$، دست کم یکی از دو راس $x_i$ و $y_i$ با یال به رنگ $j$‌مجاور است.

ثابت کنید $n$‌ زوج است.

  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]