Matematické Fórum

Nu, nejde to.

Proč? Opísmenkujme si obrázek:



S bodem D sousedí lichý počet čar, konkrétně pět. Nemůžu jít dvakrát po stejné čáře, takže když do tohohle bodu vstoupím po jedné čáře, musím ho opustit po jiné -- můžu do něj táhnout tužkou dvakrát a opět ven z něj dvakrát. Ale potřebuju do něj táhnout pětkrát -- je tam pět čar. Pátý tah do bodu D můžu udělat až na konec -- až nebudu potřebovat tužkou odjet nikam dál.

Dobrá, tedy. Ale bod F je stejný případ -- dvakrát do něj, dvakrát z něj a na popáté už z něj nemůžu. Tak v bodě F kreslení začnu -- jednou z něj, jednou dovnitř, jednou ven, jednou dovnitř, jednou ven -- to je pět čar, přesně kolik potřebuju.

Takže musím začít v bodě F a skončit v bodě D. Nebo naopak, to je jedno.

Ale body H a B jsou stejné případy -- sousedí s nimi pět čar. Ale počáteční i koncový bod už mám vybraný. Takže třeba do bodu H vjedu tužkou jednou, pak ho opustím po jiné čáře. Pak se do něj vrátím po další čáře a opustím ho po ještě jiné. No ale pak se do něj vrátím po páté po poslední čáře a už nemám jak se z něj dostat. Kreslení jsem ještě nedokončil -- končím v bodě D nebo F, nikoliv H. Nemůžu se z toho bodu dostat, aniž bych opakoval tah po stejné čáře.

Achjo. Nejde mi to dokazování dneska. Možná někdo dokáže sepsat srozumitelnější odůvodnění, že to nejde?

↑ teolog:

Přesně tak. Když mám právě dva body s lichým stupněm tak je to v pořádku. Editoval jsem svůj příspěvek už asi podruhé. Teď by to snad mělo být v pořádku, ale nejsem si jistý jestli to je pochopitelné.

↑ teolog:

Jako podmínka nutná je to jednoduché. Je zajímavé, že je to dokonce podmínka postačující: platí totiž i obrácená implikace. Pokud je počet vrcholů, do kterých vede lichý počet hran, roven nule nebo dvěma, pak se dá obrázek (graf) nakreslit jedním tahem. Tady je důkaz poněkud složitější -- tím spíš ve vší obecnosti.