Masalah Teori Grafik IMO 1990
Jadi saya melihat solusi ini untuk IMO 1990 P2:
Soal 2: Misalkan n≥3, dan misalkan S adalah himpunan 2n − 1 titik berbeda pada sebuah lingkaran. Asumsikan bahwa tepat k titik S diwarnai hitam. Pewarnaan S disebut "baik" jika terdapat setidaknya satu pasang titik hitam sedemikian rupa sehingga bagian dalam salah satu busur di antara pasangan tersebut mengandung tepat n titik S. Tentukan nilai k terkecil sehingga setiap pewarnaan dari Jadilah "baik".
Solusi: Pertimbangkan graf G yang simpulnya mewakili titik-titik dan ada tepi di antara dua simpul jika interior salah satu busur yang mereka definisikan memiliki tepat n simpul. Kami ingin menunjukkan bahwa saat kami mewarnai k simpul, dua simpul yang berdekatan telah diwarnai. Karena derajat setiap simpul adalah 2, Latihan 4.1.4 menunjukkan bahwa G adalah gabungan dari siklus-siklus yang tidak saling berhubungan. Perhatikan bahwa jika kita menomori simpul dari 1 hingga 2n - 1, maka 1 bersebelahan dengan n + 2 dan n + 2 bersebelahan dengan 2n + 3, yang merupakan simpul 4. Jadi 1 dan 4 berada dalam satu siklus yang sama. Jika 2n - 1 tidak habis dibagi 3, maka G hanya terdiri dari satu siklus, jadi k = n jelas merupakan bilangan yang diinginkan. Jika 2n − 1 habis dibagi 3, maka grafik tersebut dibentuk oleh tiga siklus terputus-putus dengan panjang 2n − 1 3. Jadi kita bisa mewarnai paling banyak 2n − 1 3 −1 2 = n − 2 3 simpul dari satu siklus tanpa mewarnai simpul yang berurutan. Jadi k = 3 · ((n - 2) / 3) + 1 = n - 1 adalah bilangan yang kita inginkan dalam kasus ini.
Saya tidak mengerti mengapa dikatakan bahwa setiap simpul akan memiliki DERAJAT 2, dapatkah seseorang menjelaskan ini kepada saya?
Jawaban
Derajat adalah banyaknya simpul lain yang memiliki ujung-ujung yang terhubung ke setiap simpul. Dalam kasus ini, dua simpul terhubung ditemukan dengan menghitung n + 1 titik di setiap arah sepanjang lingkaran.