Politikus berteman dengan semua orang

Para Politikus di DPR

Di dalam Teori Graph , ada satu teorema yang cukup elegan, yang menjelasakan fenomena unik yang bisa saja terjadi didalam hubungan bermasayarakat. Teorema tersebut dinamakan Teorema Pertemanan (Frienship Theorem). secara informal Teorema pertemanan menyatakan :

Dalam suatu komunitas, jika setiap 2 orang mempunyai tepat 1 teman bersama maka ada 1 orang (disebut Politikus) yang berteman dengan semua orang di komunitas tersebut.

Nah… yang saya maksud dengan berteman adalah saling mengenal. Budi dan bejo berteman artinya Budi dan Bejo saling mengenal. Jika kita menganggap komunitas sebgai graph sedangkan orang-orang didalamnya direpresentasikan dengan titik. Lalau 2 orang berteman bisa direpresentasikan sebgai 2 titik yang berdekatan (adjacent) maka secara formal teorema pertemanan menyatakan:

Teorema Pertemanan (TP): Diberikan graph berhingga $G$ , jika setiap 2 titik di $G$ mempunjyai tepat 1 tetangga bersama maka terdapat 1 titik yang berdekatan dengan semua titik di $G$ .

Perlu dicatat bahwa ada graph yang memenuhi TP, yaitu graph kincir angin (Windmill Graph) perhatikan gambar disamping, kincir angin graph dengan $u$ adalah politikus. Bahkan Graph kincir angin adalah satu-satunya graph yang memenuhi TP. Karena keberadaan politikus hanya dimungkinkan dengan graph Kincir angin.

Yang amat menarik ternyata TP tidak berlaku untuk graph tak-hinga, Dengan kata lain ada graph tak-hingga yang setiap pasang titiknya mempunyai 1 tetangga bersama tetapi tanpa adanya politikus. Untuk mengkontruksikan Graph tak-hingga seperti itu mudah saja. bisa kita mulai dengan 5-siklik kemudian terus tambahkan 1 tetangga bagi setiap pasang titik yang belum mempunyai tetangga bersama

Bukti :

Ada banyak cara membuktikan TP tetapi saya akan menggunakan cara dari Paul Erdős, Alfréd Rényi, and Vera T. Sós. Merekalah yang pertamakali menerbitkan TP. Akan dibuktikan dengan cara kontradiksi. Dinotasikan $G$ graph berhingga dengan setiap pasang titiknya mempunyai 1 tetangga bersama tetapi tanpa ada politikus. Akan ditunjukkan $G$ menimbulkan kontradiksi.

Kita akan membuktikan dengan 2 langkah:

4-siklik

Langkah (1): Akan dibuktian bahwa $G$ adalah regular yaitu semua titik mempunyai derajat yang sama. Perlu diperhatikan bahwa antiseden dari TP mengakibatkan tidak ada 4-siklik di $G$ , kita sebut saja Kondisi-C4. Pertama-tama kita akan menunjukkan bahwa setiap 2 titik yang tidak berdekatan $u$ dan $v$ mempunyai derajat yang sama $d\left(u\right)=d\left(v\right)$ . Andaikan $d\left(u\right)=k$ , dengan $w_{1},\ldots w_{k}$ adalah tetangga dari $u$ . Berdasakan antiseden TP maka salah-satu dari $w_i$ , sebut saja $w_2$ berdekatan ke $v$ dan $w_2$ berdekatan dengan salah satu $w_i$ lainnya sebut saja $w_1$ . Kondisi tersebut diilustrasikan dengan gambar di bawah:

graph2

Titik $v$ dan $w_1$ mempunyai tetangga bersama $w_2$ . Sedangkan $v$ dan $w_{i},\,\left(i\geq2\right)$ mempunyai tetangga bersama $z_{i},\,\left(i\geq2\right)$ . Berdasarkan kondisi-C4, semua $z_i$ haruslah berbeda. Disimpulkan

$d\left(u\right)\geq k=d\left(v\right)$ , berdasarkan simetri diperoleh $d\left(u\right)=d\left(v\right)=k$

Untuk menyelesaikan pembuktian, dapat diamati bahwa sebarang titik yang berbeda dari $w_2$ tidak berdekatan dengan $u$ maupun $v$ dan mempunyai derajat $k$ berdasarkan apa yang telah kita buktikan diatas. Begitupula $w_2$ mempunyai titik-titik tak bertetangga juga berderajat $k$ . Itu berarti $G$ adalah reguler-k.

Jumlahkan semua k tetangga dari dari $u$ diperoleh $k^2$ . Karena setiap titik (kecuali $u$ ) mempunyai 1 tetangga bersama dengan $u$ . Telah dihitung setiap titik sebanyak sekali kecuali untuk $u$ yang dihitung $k$ kali. Jadi banyaknya titik di $G4$ adalah:

$n=k^2-1$ (i)

Langkah (2): Berdasarkan persamaan (i), diketahui nilai $k$ haruslah lebih besar daripada 2. Karena untuk $k\leq2$ diperoleh $G=K_1$ dan $G=K_2$ yang hanya merupakan graph kincir angin trivial. Selanjutnya akan dibahas Matriks adjacency $A$ . Berdasarkan Langkah (1) Setiap baris mempunyai 1 tepat sebanyak k. Berdasafrkan anteseden TP, untuk setiap 2 baris tepat terdapat 1 kolom yang keduanya bernilai 1, sedangkan diagonal utamnya bernilai 0, diperoleh :

$A^{2}=\left[\begin{array}{cccc}k & 1 & \ldots & 1\\1 & k & & 1\\\vdots & & \ddots & \vdots\\1 & \cdots & 1 & k\end{array}\right]=\left(k-1\right)I+J$ .

Dari ekspresi diatas diketahui bahwa $A^2$ mempunyai nilai eigen $n+k-1=k^2$ dan $k-1$ muncul sebanyak $n-1$ kali. Nilai eigen dari $A^2$ adalah kuadrat dari nilai eigen $A$ yaitu $k$ dan $\pm\sqrt{k-1}$ . Diketahui $tr\left(A\right)=0$ dan penjumlahan nilai-nilai eigen $A$ sama dengan $tr\left(A\right)$ . Jika $\sqrt{k-1}$ muncul sebanyak $r$ kali dan $\sqrt{k-1}$ muncul sebanyak $s$ kali diperoleh

$k+\left(r-s\right)\sqrt{k-1}=0$

Berakibat $k^{2}=\left(r-s\right)^{2}\left(k-1\right)$ yang berarti $k-1$ membagi $k^2$ . Karena $k$ adalah bilangan bulat maka solusi yang mungkin hanyalah $k=1,2$ . Diperoleh graph $K_1$ dan $K_2$ , padalaha dari yang telah kita bahas diatas kedua graph tersebut telah dikecualikan, didapat Kontradiksi maka pembutian telah lengkap.