Obseg (teorija grafov): Razlika med redakcijama

Za poljubni pozitivni celi števili ''g'' in χ obstaja graf z notranjim obsegom vsaj ''g'' in [[kromatično število|kromatičnim številom]] vsaj χ. [[Grötzschev graf]] na primer nima trikotnikov, njegovo kromatično število je enako 4. S ponavljanjem konstrukcije [[graf Mycielskega|Mycielskega]] lahko iz Grötzschevega grafa dobimo grafe brez trikotnikov s poljubno velikim kromatičnim številom. [[Paul Erdős]] je prvi [[matematični dokaz|dokazal]] splošni rezultat s pomočjo [[verjetnostna metoda|verjetnostne metode]].<ref>Erdős (1959).</ref> Pokazal je, da [[naključni graf]] na ''n'' točkah, ki je nastal z neodvisno izbiro vsake povezave z [[verjetnost]]jo ''n''^{(1&nbsp;−&nbsp;''g'')/''g''}, ima, če verjetnost teži k 1, ko gre ''n'' k neskončnosti, največ ''n''/2 ciklov dolžine ''g'' ali manj, vendar nima [[neodvisna množica (teorija grafov)|neodvisne množice]] velikosti ''n''/2''k''. Če odstranimo eno točko iz vsakega kratkega cikla, zato dobimo manjši graf z notranjim obsegom večjim od ''g'', v katerem mora biti vsak barvni razred barvanja majhen in zaradi tega potrebuje vsaj ''k'' barv v vsakem [[barvanje grafa|barvanju]].