Archiv diskusního fóra o matematice, 2006–2026
Dobrý deň,
vedeli by ste mi niekto prosím Vás poradiť ako postupovať pri takomto dôkaz?
Nech G je graf na n vrcholoch s m hranami. Dokážte, že χ(G)≥n^2/(n^2−2m).
Ďakujem
Offline
Ahoj, ja bych zacal tak, ze bych si rozmyslel, jak vypada graf, ktery pro dane X(G) a n ma maximalni pocet hran.
Dosel bych k zaveru, ze takovy graf ma priblizne stejny pocet vrcholu (p nebo p+1) ruznych barev, tj
a vsechny ruzne barevne vrcholy jsou spojeny. Pocet hran, ktere chybi do uplneho grafu je pak rovny poctu hran,
ktere je nutno pridat mezi stejnebarevne vrcholy a plati tedy odhad
[mathjax] {\displaystyle \binom{n}{2}-m \;\; \geq \;\; \bigr(\chi(G)-q\bigr)\cdot\binom{p}{2} + q\cdot\binom{p+1}{2}} [/mathjax]
Dosadime-li za
, ziskame
[mathjax] {\displaystyle \binom{n}{2}-m \;\; \geq \;\; \bigr((p+1)\cdot\chi(G)-n\bigr)\cdot\binom{p}{2} + \bigr(n-p\cdot\chi(G)\bigr)\cdot\binom{p+1}{2} }[/mathjax]
coz lze prepsat na 
a staci tedy ukazat, ze plati
coz lze zapsat jako
Prvni zavorka je rovna
a je urcite nezaporna, druha zavorka je rovna [mathjax] {\displaystyle 1-\frac{q}{\chi(G)}\geq \frac{1}{\chi(G)}>0 }[/mathjax].
Offline