Prinsip Sangkar Burung: Dua Titik Berderajat Sama Pada Graf Sederhana

Problem

Andaikan $G$ adalah sebuah graf sederhana (simple graph). Bila $e$ adalah sebuah sisi yang menghubungkan titik $u$ dan $v$ di $G$, maka dikatakan bahwa titik $u$ bertetangga dengan titik $v$. Derajat dari sebuah titik $v$ di $G$ adalah banyaknya titik-titik yang bertetangga dengan $v$. Perlihatkan bahwa pada sebuah graf sederhana $G$ terdapat sedikitnya dua titik dengan derajat sama.
[ON MIPA-PT Matematika 2018, Tingkat Wilayah]

Solusi

Misalkan $G$ adalah graf sederhana dengan $n$ titik dan $x$ adalah sebarang titik pada $G$. Terdapat $n-1$ titik yang dapat bertetangga dengan $x$. Akibatnya, derajat yang mungkin dari $x$ adalah anggota dari $$\{ 0,1,2,\ldots,n-1 \}$$

Perhatikan bahwa graf $G$ tidak mungkin memuat dua titik dengan derajat 0 dan $n-1$ secara bersamaan. Artinya, jika $G$ mempunyai sebuah titik dengan derajat 0 maka pasti tidak ada titik lain dengan derajat $n-1$. Begitupun sebaliknya. Hal ini dapat dibuktikan dengan kontradiksi. Andaikan $G$ memuat titik $a$ dan $b$, yang secara berturut-turut berderajat 0 dan $n-1$. Titik $b$ memiliki derajat $n-1$, artinya titik $b$ bertetangga dengan semua titik lain pada $G$, termasuk $a$. Akibatnya, derajat dari titik $a$ minimal 1. Terjadi kontradiksi.

Dengan demikian, derajat yang mungkin dari titik-titik pada $G$ adalah anggota dari $$\{0,1,\ldots,n-2\} \text{ atau } \{1,2,\ldots,n-1\}$$ Keduanya merupakan himpunan dengan $n-1$ anggota. Karena $G$ terdiri dari $n$ titik, maka berdasarkan Prinsip Sangkar Burung, terdapat sedikitnya dua titik yang memiliki derajat sama. Terbukti.


Bagikan ke:
Click here if solved
Click here to save

Maaf, fitur ini hanya untuk pembaca yang telah terdaftar. Silakan Masuk atau buat akun terlebih dahulu.

Tambah Komentar