
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 , jika setiap 2 titik di
mempunjyai tepat 1 tetangga bersama maka terdapat 1 titik yang berdekatan dengan semua titik di
.
Perlu dicatat bahwa ada graph yang memenuhi TP, yaitu graph kincir angin (Windmill Graph) perhatikan gambar disamping, dengan
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 graph berhingga dengan setiap pasang titiknya mempunyai 1 tetangga bersama tetapi tanpa ada politikus. Akan ditunjukkan
menimbulkan kontradiksi.
Kita akan membuktikan dengan 2 langkah:

4-siklik
Langkah (1): Akan dibuktian bahwa adalah regular yaitu semua titik mempunyai derajat yang sama. Perlu diperhatikan bahwa antiseden dari TP mengakibatkan tidak ada 4-siklik di
, kita sebut saja Kondisi-C4. Pertama-tama kita akan menunjukkan bahwa setiap 2 titik yang tidak berdekatan
dan
mempunyai derajat yang sama
. Andaikan
, dengan
adalah tetangga dari
. Berdasakan antiseden TP maka salah-satu dari
, sebut saja
berdekatan ke
dan
berdekatan dengan salah satu
lainnya sebut saja
. Kondisi tersebut diilustrasikan dengan gambar di bawah:
Titik dan
mempunyai tetangga bersama
. Sedangkan
dan
mempunyai tetangga bersama
. Berdasarkan kondisi-C4, semua
haruslah berbeda. Disimpulkan
, berdasarkan simetri diperoleh
Untuk menyelesaikan pembuktian, dapat diamati bahwa sebarang titik yang berbeda dari tidak berdekatan dengan
maupun
dan mempunyai derajat
berdasarkan apa yang telah kita buktikan diatas. Begitupula
mempunyai titik-titik tak bertetangga juga berderajat
. Itu berarti
adalah reguler-k.
Jumlahkan semua k tetangga dari dari diperoleh
. Karena setiap titik (kecuali
) mempunyai 1 tetangga bersama dengan
. Telah dihitung setiap titik sebanyak sekali kecuali untuk
yang dihitung
kali. Jadi banyaknya titik di
adalah:
(i)
Langkah (2): Berdasarkan persamaan (i), diketahui nilai haruslah lebih besar daripada 2. Karena untuk
diperoleh
dan
yang hanya merupakan graph kincir angin trivial. Selanjutnya akan dibahas Matriks adjacency
. 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 :
.
Dari ekspresi diatas diketahui bahwa mempunyai nilai eigen
dan
muncul sebanyak
kali. Nilai eigen dari
adalah kuadrat dari nilai eigen
yaitu
dan
. Diketahui
dan penjumlahan nilai-nilai eigen
sama dengan
. Jika
muncul sebanyak
kali dan
muncul sebanyak
kali diperoleh
Berakibat yang berarti
membagi
. Karena
adalah bilangan bulat maka solusi yang mungkin hanyalah
. Diperoleh graph
dan
, padalaha dari yang telah kita bahas diatas kedua graph tersebut telah dikecualikan, didapat Kontradiksi maka pembutian telah lengkap.
QED
KEREN!!!