Matematické Fórum

nordec · 06. 05. 2010 18:05

Zdravím, potřebuji poradit, jestli můžu v důkazu takto postupovat.
Zadání: Dokažte, že $\chi(G) \ge \Delta(G)$ . ( $\Delta(G)$ je maximální stupeň vrcholu v grafu G, $\chi(G)$ značí nejmenší hranové obarvení grafu G takové, že každé dvě sousední hrany mají různou barvu)

Důkaz by měl 3 části, které postupně ověřím:
1) $\chi(G) \lt \Delta(G)$
2) $\chi(G) = \Delta(G)$
3) $\chi(G) \gt \Delta(G)$

1) pokud $\chi(G) \lt \Delta(G)$ , pak by z vrcholu, z něhož vede $\Delta(G)$ hran, musely vést aspoň 2 stejně barevné hrany => podmínka pro hranové obarvení je porušena, a proto $\chi(G) \lt \Delta(G)$ neplatí.
Pro 2) a 3) najdu nějaké dva grafy (k 1 podmínce 1 graf), které toto splňují, a proto 2) a 3) platí.
Původní tvrzení $\chi(G) \ge \Delta(G)$ tedy platí.

petrkovar

↑ nordec:Ano. V podstatě stačí ukázat 1), neboť když vyvrátíme $\chi'(G) < \Delta(G)$ , tak musí platit opačné tvrzení, čili $\chi'(G) \geq \Delta(G)$ .
(chromatický index se obvykle značí $\chi'(G)$ , bez čárky to je chromatické číslo, které souvisí s vrcholovým barvením grafu $G$ )

nordec · 07. 05. 2010 16:05

↑ petrkovar:
Jsem rád, že ten důkaz funguje. Díky za připomínky.

Matematické Fórum

#1 06. 05. 2010 18:05

Důkaz - hranové obarvení grafu

#2 06. 05. 2010 22:50 — Editoval petrkovar (06. 05. 2010 22:50)

Re: Důkaz - hranové obarvení grafu

#3 07. 05. 2010 16:05

Re: Důkaz - hranové obarvení grafu

Zápatí