Matematické Fórum

Dobrý den, byl bych moc vděčný za pomoc s tímto důkazem:

,,Dokažte, že χ(G) ≤ n právě tehdy když existuje homomorfismus z grafu G do Kn."


víme, že: χ(G) ... značí minimum barev potřebných k vrcholovému zabarvení grafu o n vrcholech
             
               Kn ... je kompletní graf o n - vrcholech

důkaz jsem tedy rozdělil na 2 části: a) χ(Kn) = n
                                                        - jelikož se jedná o kompletní graf o n - vrcholech, je potřeba použít n barev
                                                        - deg(v) = n, pro všechny v náležící V(G) (při zobrazení se zachovávají stupně vrcholů)
                                                        - Nechť tedy existuje homomorfismus G → Kn. Pak pro každý vrchol v z G existuje právě jeden vrchol v´ z Kn (platí v → v´)
                                                        - z toho vyplývá, že |V(G)| ≤ |V(Kn)| (každý vrchol z G se musí mít na co zobrazit)
                                                        - dále Kn má n - vrcholů (z definice kompletního grafu) ... z toho plyne, že G musí mít ≤ n vrcholů
                                                        - z toho tedy závěrem vyplývá, že počet barev k obarvení vrcholů z G je ≤ n: tedy χ(G) ≤ n  ✓

                                                    b) Nechť χ(G) ≤ n (potom počet vrcholů je ≤ n) ... |V(G)| ≤ n
                                                        - dále v Kn (kompletním grafu) platí, že máme n vrcholů, které jsou všechny vzájemně pospojovány (musíme tedy mít n barev
                                                          pro obarvení tohoto grafu Kn)
                                                        - potom existuje INJEKCE z G na Kn  ✓

při kontrole mi však bylo vytknuto následující: část a) Jestli máme homomorfismus, nemusí platit, že |V(G)| ≤ |V(Kn)| a graf nemusí mít tedy méně jak n vrcholů
                                                                   část b) Stejně tak, jestli máme χ(G) ≤ n tak potom nemusí platit |V(G)| ≤ n

                                                                  pozn. Jako příklad si můžeme vzít cestu P na n vrcholech (potom  χ(P) = 2).

Nevěděl by mi prosím někdo poradit jak tento důkaz správně přeformulovat, případně jak na to jít jinou cestou ?
Předem děkuji za jakoukoliv radu.