Feladat: 1.7.
Egy gyár hat különböző színű fonalból kétszínű kelmét gyárt. Minden szín legalább háromféle párosításban szerepel. Bizonyítandó, hogy kiválasztható háromféle kelme úgy, hogy mindegyik szín előfordul valamelyikben. (Kürschák verseny, 1957. l. [
176])
Megoldás: 1.7
1. megoldás.
Válasszunk ki egy kelmét, ennek színeit nevezzük el 1-esnek és 2-esnek. Vegyünk egy másik színt, ez biztosan szerepel párban egy, az 1-estől és 2-estől különböző színnel (különben csak kétféle kelmében fordulna elő). Legyenek ennek a kelmének a színei tehát 3 és 4. Ha a kimaradt ötödik és hatodik szín szerepel együtt valamelyik kelmén, már kész is vagyunk. Ellenkező esetben mind az 5-ös szín, mind a 6-os szín az 1-es, 2-es, 3-as és 4-es szín közül hárommal szerepel együtt. Szimmetria okokból feltehetjük, hogy például az 5-ös szín az 1-essel és a 2-essel is szerepel. Ám a 6-os színnek is kell valamelyikkel együtt szerepelnie. Ha például az 1-essel szerepel együtt, akkor az 1,6, a 2,5 és a 3,4 színű kelmék megfelelnek. Ha a 2-essel, akkor a 2,6, 1,5 és a 3,4 kelmék megfelelőek.
2. megoldás.
Vegyük észre, hogy ez a feladat szinte azonos a
K.II.9.10. feladattal. Az ottani ismeretségnek az itteni kelmék felelnek meg. Gráfelméleti nyelven megfogalmazva a különbséget: ott azt mondtuk, hogy minden pont foka három, itt azt mondjuk, hogy minden pont foka legalább három.