Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#2 22. 04. 2010 10:40
Re: Barvení grafu
↑ kajbl:Šel bych na úlohu konečnou indukcí.
Mějme libovolné obarvení vrcholů grafu dvěma barvami.
Pokud splňuje podmínky zadání, tak důkaz končí. Pokud existuje jednobarevná cesta, přebarvíme její vnitřní vrchol.
Pozor! Tím může vzniknout další jednobarevná cesta! (opačné barvu) Ale když pečlivě spočítáme jednobarevné hrany před a po přebarvení, najdeme argument, že opakováním takového postupu dřív nebo později dostaneme hledané barvení.
Offline