Matematické Fórum

↑ honza33:Pro spor předpokládejme, že to jde. Nakresleme si doplněk grafu. Protože v grafu nejsou spojnice (1,2),(2,3)...(8,9), musí být všechny tyto spojnice v doplňku. A když se na ten obrázek doplňku podíváme [edit: zavádějící poznámka umazána] tak vidíme, že jsme již došli ke sporu.

↑ honza33:Souhlasím.

Ale vždyť jde připsat k tomu doplňku čísla 1-9 tak aby nebyli sousedé u sebe. Doplněk je tvořen z dvou podgrafu K5 a K4 .. tzn když vložím do K5 všechna lichá čísla a do K4 všechna sudá, tak dokážu že to lze! Nebo se snad mýlím?

No snažíme se tu ověřit že do grafu za pomocí doplňku neuspořádáme čísla 1-9, aby sousede nebyli spojeni hranou. A podle vašich postu jsem pochopil že jste to vyvrátili. A já právě tvrdím že to jde.

↑ Kondr:Já myslím, že mosty v Königsbergu (Kaliningradě) jsou spíš zavádějící. už jsem dostal řešení, které se odvolávalo na to, že neexistuje eulerovský tah v doplňku. To pro řešení úlohy není podstatné, protože v doplňku nehledáme eulerovský tah (=tah, který projde každou hranu doplňku právě jednou). Nám nejde o to projít všechny hrany nějakého grafu, ale všechny vrcholy - vždyť číslujeme vrcholy a ne hrany! Kdybychom prošli všechny hrany, tak se nám vrcholy v tahu budou (v grafu podle zadání) opakovat!