Matematické Fórum

↑ El267:

Ahoj, rozlis pripady, kdy [mathjax]G[/mathjax] je souvisly a kdy neni souvisly:

I) [mathjax]G[/mathjax] je souvisly

Postupuj indukci vzhledem k [mathjax]n[/mathjax]. Ukaz, ze to plati pro [mathjax]n=3[/mathjax] (pro [mathjax]n=2[/mathjax] neexistuje souvisly graf splnujici predpoklad [mathjax]\chi(G)=1[/mathjax]). Predpokladej, ze tvrzeni plati pro vsechny grafy, ktere maji pocet vrcholu [mathjax]n-1[/mathjax] a chromaticke cislo [mathjax]n-2[/mathjax], a uvazuj graf [mathjax]G[/mathjax] na [mathjax]n[/mathjax] vrcholech s [mathjax]\chi(G)=n-1[/mathjax]. Zrejme graf [mathjax]G[/mathjax] neni uplny (jinak by mel [mathjax]\chi(G)=n[/mathjax]) a nejedna se ani o kruznici liche delky (ta ma [mathjax]\chi(G)=3=n-1[/mathjax], takze by muselo byt [mathjax]n=4[/mathjax], coz neni liche). Podle Brooksovy vety (plati jen pro souvisle grafy, takze proto to rozliseni na souvisle a nesouvisle grafy) je tedy [mathjax] \Delta(G) \geq \chi(G) = n-1[/mathjax]. V grafu [mathjax]G[/mathjax] proto existuje vrchol [mathjax]v[/mathjax] se stupnem [mathjax]\mathrm{deg}_G(v)=n-1[/mathjax], tj vrchol spojeny se vsemi ostatnimi vrcholy. Pri obarveni grafu [mathjax]G[/mathjax] pomoci [mathjax]n-1[/mathjax] barev je tedy barva vrcholu [mathjax]v[/mathjax] odlisna od barev vsech ostatnich vrcholu. Odebereme-li nyni vrchol [mathjax]v[/mathjax], ziskame graf [mathjax]\widetilde{G}=G\setminus v[/mathjax], pro ktery plati [mathjax]\chi(\widetilde{G})=n-2.[/mathjax] Podle indukcniho predpokladu je [mathjax]\omega(\widetilde{G})=n-2[/mathjax] a v grafu [mathjax]\widetilde{G}[/mathjax] tedy existuje klika velikosti [mathjax]n-2[/mathjax]. To ale znamena, ze v puvodnim grafu [mathjax]G[/mathjax] musela existovat klika velikosti alespon [mathjax]n-1[/mathjax]. Vrchol [mathjax]v[/mathjax] byl totiz spojen se vsemi zbylymi vrcholy. Tedy [mathjax]\omega(G)\geq n-1[/mathjax]. Protoze [mathjax]G[/mathjax] neni uplny, musi byt [mathjax]\omega(G)\leq n-1[/mathjax], a proto [mathjax]\omega(G)= n-1[/mathjax].

II) [mathjax]G[/mathjax] neni souvisly

Jelikoz je [mathjax]\chi(G)=n-1[/mathjax], musi graf [mathjax]G[/mathjax] obsahovat komponentu s alespon [mathjax]n-1[/mathjax] vrcholy. Jinak by nutne bylo [mathjax]\chi(G)<n-1[/mathjax]. Zaroven nemuze obsahovat komponentu s vice nez [mathjax]n-1[/mathjax] vrcholy, protoze by pak byl souvisly. Graf [mathjax]G[/mathjax] je tedy tvoren dvema komponentami - izolovanym vrcholem a komponentou majici [mathjax]n-1[/mathjax] vrcholu. Protoze je ale [mathjax]\chi(G)=n-1[/mathjax], je [mathjax](n-1)[/mathjax]-prvkova komponenta uplnym podgrafem - tedy klikou. A proto je  [mathjax]\omega(G)= n-1[/mathjax].