Matematické Fórum

Dukaz povedeme sporem. Mejme minimalni kostru grafu G. Pokud tato kostra bude mit nejaky vrchol stupne alespon 7, ukazeme, ze existuje kostra mensi.

Oznacme 'c' ten vrchol, jenz ma n>6 sousedu. Jeho sousedy oznacme v_1, v_2, ..., v_n. Prepokladejme, ze zadne tri z vrcholu c, v_1, ..., v_n nelezi na usecce, s krajnim bodem 'c'. Reseni pripadu, kdy toto nastane prenechavam ctenari. Poloprimky c-v_1, c-v_2, ..., c-v_n deli rovinu na 'n' disjunktnich uhlu (disjunktnich v tom smyslu, ze maji spolecne pouze hranicni poloprimky). Je evidentni, ze soucet techto uhlu musi byt roven 360°, tedy alespon jeden z techto uhlu musi byt ostre mensi nez 60°. Vezmene tento uhel a uvazujme trojuhelnik tvoreny z vrcholu tento uhel definujicich. Jeden z techto vrcholu je 'c', dalsi dva oznacme v_x, v_y. Jelikoz uhel u vrcholu 'c' je ostre mensi nez 60°, nejvetsi uhel v tomto trojuhelniku je u jednoho z vrcholu v_x nebo v_y. Proti tomuto uhlu take lezi nejdelsi usecka tohoto trojuhelnika. Je to tedy jedna z usecek c-v_x nebo c-v_y. Bez ujmy na obecnosti prepokladejme, ze je to usecka c-v_x. Jelikoz je nejdelsi, usecka v_x-v_y je kratsi nez ona. Lze tedy v kostre grafu G nahradit hranu c-v_x hranou v_x-v_y. Dostaneme tak mensi kostru. (Tady je samozrejme treba dokazat, za takto vznikla kostra vubec kostrou je, tedy ze to je strom. Toto opet nechavam na ctenari).

Ufff, tak jak jsem to napsal to vypada strasne slozite, ale neni. Hlavni myslenka je velmi jednoducha, nejlip je to videt na obrazku, bohuzel nejsem zrovna u pocitace, ktery by mel nejaky solidni kreslici program, takze jsem to musel napsat takto slovy. Treba se najde nekdo, kdo to pochopi a nakresli to za me.