Matematické Fórum

hint k 4) indukcí. Pro K_2 a K_4 to jistě zvládneme. Předpokládejme, že to umíme pro K_n a doážeme to pro K_(2n). Z grafu K_n získáme K_(2n) tak, že graf zdvojíme, tedy místo každého vrcholu A_i budeme mít dva, A_i a B_i. Hrany mezi dvojicemi vrcholů A_i,A_j rozdělíme do n-1 párování tak, jak byly v původním grafu. Pokud do nějakého párování dáváme hranu A_i, A_j, dáme tam i hranu B_i, B_j. Tak nám vznikne n-1 párování, každé obsahuje dvakrát více hran, než to původní. Dále ke každému z těchto n-1 párování vyrobíme párování "komplementární" -- pokud vzor obsahuje hrany A_i,A_j a B_i,B_j, bude komplement obsahovat hrany A_i,B_j a B_i,A_j. Snadno rozmyslíme, že i tato párování jsou kompletní a že jsou disjunktní s dříve sestrojenými. Poslední párování, které přidáme, spojuje vždy vrchol A_i s vrcholem B_i. Vytvořili jsme tak celkem 2n-1 disjunktních párování, každé obsahuje n hran, je tak pokryto všech (2n nad 2) hran grafu K_(2n), indukční krok je hotov a důkaz také. Tak to byl nakonec víc než hint ;)

k 3)b) -- úloha skoro vybízí k tomu, abys hledal protipříklad. Stačí zkusit malá n, třeba n=2.