Prinsip Sangkar Burung: Graf G atau Komplemennya Memuat Subgraf Lengkap $K_3$

Problem

Suatu graf $\Lambda$ disebut komplemen dari graf $\Gamma$ jika $V(\Lambda)=V(\Gamma)$ dan sisi $e=(u,v) \in E(\Lambda)$ jika dan hanya jika sisi $e=(u,v) \notin E(\Gamma)$. Komplemen dari graf $\Gamma$ ditulis $\overline{\Gamma}$. Tentukan bilangan positif terkecil $N$ sedemikian sehingga untuk sebarang graf $\Gamma$ dengan $N$ titik senantiasa memuat graf lengkap $K_3$ sebagai subgraf atau graf $\overline{\Gamma}$ memuat graf lengkap $K_3$ sebagai subgraf. Kemudian, buktikan.
[ON MIPA-PT Matematika 2015, Tingkat Wilayah]

Solusi

Dalam solusi ini, kita memanfaatkan salah satu akibat dari Prinsip Sangkar Burung yang Diperumum.

Prinsip Sangkar Burung yang Diperumum

Misalkan $q_1,q_2,\ldots,q_n$ adalah bilangan bulat positif. Jika $$q_1+q_2+\ldots+q_n-n+1$$ objek didistribusikan ke dalam $n$ kotak, maka kotak pertama memuat $q_1$ objek atau kotak kedua memuat $q_2$ objek, $\ldots$, atau kotak ke-$n$ memuat $q_n$ objek.

Akibat 1

Misalkan $n$ dan $r$ adalah bilangan bulat positif. Jika $n(r-1)+1$ objek didistribusikan ke dalam $n$ kotak, maka sedikitnya satu kotak memuat $r$ atau lebih objek.

Kita klaim bahwa bilangan positif terkecil $N$ yang memenuhi adalah 6.

Misalkan $\Gamma$ adalah sebarang graf dengan $6$ titik, dan $w$ adalah salah satu titik pada $\Gamma$. Lima titik lain dapat bertetangga atau tidak dengan $u$. Misalkan $A$ himpunan titik pada $\Gamma$ yang bertetangga dengan $w$ dan $B$ himpunan titik yang tidak bertetangga dengan $w$.

Kita akan mendistribusikan lima titik ke dalam dua himpunan. Perhatikan bahwa $5=2(3-1)+1$. Berdasarkan akibat 1, terdapat sedikitnya satu himpunan yang memuat tiga atau lebih titik. Artinya, salah satu dari kemungkinan berikut terjadi.

  1. Sedikitnya tiga titik bertetangga dengan $w$
  2. Sedikitnya tiga titik tidak bertetangga dengan $w$

Tanpa mengurangi perumuman, kita asumsikan bahwa kasus pertama terjadi. Bukti untuk kasus kedua identik dengan kasus pertama. Misalkan tiga titik yang bertetangga dengan $w$ adalah $x,y,z$. Jika di antara $x,y,z$ terdapat dua titik yang bertetangga, misalnya $x$ dan $y$, maka titik $w$, $x$, dan $y$ membentuk graf lengkap $K_3$. Dengan demikian, $\Gamma$ memuat graf lengkap $K_3$ sebagai subgraf.

Namun, bagaimana jika di antara $x,y,z$ tidak ada yang bertetangga? Jika tidak ada, maka $(x,y),(x,z),(y,z) \notin E(\Gamma)$. Akibatnya $(x,y),(x,z),(y,z) \in E(\overline{\Gamma})$. Titik $x,y,z$ dan ketiga sisi ini membentuk subgraf dari $\overline{\Gamma}$, yang merupakan graf lengkap $K_3$. 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