Page 237 - OLİMPİK SONLU MATEMATİK

ÇÝZGE KURAMI (GRAF)

Þa yet der(A) < 3 ise her han gi iki si nin bir bi ri ni ta ný ma yan üç ki þi nin var lý ðý açýk týr.

r nek:
Ö Ör nek:
Bir par ti ye ka tý lan 605 ki þi den her bi ri en az bir ki þi ile to ka la þý yor. En az iki ki þi ile to -
ka la þan bir ki þi nin var lý ðý ný gös te ri niz.

Çö züm:
Çö züm:
605 ki þi yi tem sil eden 605 kö þe (nok ta) V , V , V ,…,
1 2 3
V ol sun. To ka la þan iki ki þi yi bir ke nar ile bað la ya rak gös -
605
te re lim. Par ti ye ka tý lan her bir ki þi en az bir ki þi ile to ka laþ -
tý ðý na gö re ve 1 k < 605, k N ol du ðu na gö re, en az iki ki -
þi ile to ka la þan bir ki þi var dýr.

Baþ ka bir de yiþ le eðer, 605 ki þi den her bi ri en az bir ki þi
ile to ka laþ mýþ ve hiç kim se en az iki ki þi ile to ka laþ ma mýþ sa her kes tam ola rak bir ki þi ile

to ka laþ mýþ de mek tir. Bu na gö re de re ce ler top la mý 605.1 = 605 olur. ol du ðun dan

bu im kan sýz dýr. Bu na gö re, En az iki ki þi ile to ka la þan bir ki þi nin var dýr.

a ným:
T Ta ným:
Ke nar la rý ke siþ me ye cek þe kil de çi zi le bi len gra fa düz lem sel graf de nir.

Yu ka rý da ve ri len graf ke nar la rý ke siþ me ye cek þe kil de çi zi le bi le ce ðin den bu graf da düz -
lem sel graf týr.

236 Tübitak Ulusal Matematik Olimpiyatlarýna Hazýrlýk