Dalam Suatu Pesta

[Louiscahyadi 17]

Dalam suatu pesta, setiap orang  mengenal sedikitnya 3 orang lain. Buktikan terdapat $n$ orang diantaranya dengan $n$ genap dan $n \geq 4$ dapat duduk di suatu meja bundar sehingga setiap orang mengenal kedua orang di sebelahnya. 

[erlang 44]

Dalam "bahasa graph":

Diberikan sebuah graph dengan $k\ge 4$ vertex, dan degree setiap vertex lebih dari sama dengan 3. Buktikan terdapat cycle dengan genap buah vertex.

[erlang 44]

Dalam pesta itu ada permainan yang sangat asik

dipilih satu orang random (orang 1)

terus pilih orang yang kenal dia untuk berdiri di belakangnya (orang 2)

pilih orang yang kenal orang dua yang belom baris untuk berdiri dibelakang orang 2 (ini orang 3)

dan selama bisa, pilih orang k+1 untuk berdiri di belakang orang k jika masih ada orang yang kenal orang k tapi belum ikut baris

terus tinggal liat barisan ini deh nanti ada cycle evennya (loh kenapa)

asik sekali kan (saya dulu pernah main permainan ini loh)

[donjar 40]

Klaim: Pasti ada cycle.

Bukti: Ambil aja terus rentetan orang-orangnya. Kan setiap orang kenalannya tiga, ntar juga pasti balik dan membentuk cycle.

 

Misalkan cycle ini ganjil. Kalau di orang-orang di cycle tersebut, ada 2 orang ga berdekatan yang kenalan, ntar cyclenya jadi kebagi, satu ganjil satu genap.

Contoh: cycle 1 - 2 - 3 - 4 - 5 - 6 - 7 - 1

Misalnya 1 kenal 5. Ntar kebagi jadi 1 - 2 - 3 - 4 - 5 - 1 dan 5 - 6 - 7 - 1 - 5. Kan ada yang ganjil dan yang genap tuh. Berarti ada deh yang genap.

 

Kalau nggak ada, berarti setiap orang punya kenalannya masing-masing. Berarti setiap orang itu bisa dibuat kelompok kenalan gitu: kelompok 1 isinya orang 1 dan kenalannya, kelompok 2 isinya 2 dan kenalannya dst... Nanti kenalannya juga punya kenalan, cabang lagi...

Kalau ada orang di kelompok a yang kenal orang di kelompok b yang bukan orang utama (di cycle utama) (which is inevitable karena banyaknya orang finite), berarti ada cycle yang nempel ke cycle utama tuh (kayak naftalen lol). either cycle barunya genap, atau ganjil --> cycle besar yang gabungin keduanya genap. hore selesai.