Editing Girth (graph theory) (section)

==Girth and graph coloring==
For any positive integers {{mvar|g}} and {{math|χ}}, there exists a graph with girth at least {{mvar|g}} and [[chromatic number]] at least {{math|χ}}; for instance, the [[Grötzsch graph]] is triangle-free and has chromatic number 4, and repeating the [[Mycielskian]] construction used to form the Grötzsch graph produces triangle-free graphs of arbitrarily large chromatic number. [[Paul Erdős]] was the first to prove the general result, using the [[probabilistic method]].<ref>{{citation | last = Erdős | first = Paul | author-link = Paul Erdős | journal = Canadian Journal of Mathematics | pages = 34–38 | title = Graph theory and probability | volume = 11 | year = 1959 | doi = 10.4153/CJM-1959-003-9| s2cid = 122784453 | doi-access = free }}.</ref> More precisely, he showed that a [[random graph]] on {{mvar|n}} vertices, formed by choosing independently whether to include each edge with probability {{math|''n''<sup>(1–''g'')/''g''</sup>}}, has, with probability tending to 1 as {{mvar|n}} goes to infinity, at most {{math|{{sfrac|''n''|2}}}} cycles of length {{mvar|g}} or less, but has no [[Independent set (graph theory)|independent set]] of size {{math|{{sfrac|''n''|2''k'' }}}}. Therefore, removing one vertex from each short cycle leaves a smaller graph with girth greater than {{mvar|g}}, in which each color class of a coloring must be small and which therefore requires at least {{mvar|k}} colors in any coloring.

Explicit, though large, graphs with high girth and chromatic number can be constructed as certain [[Cayley graph]]s of [[linear group]]s over [[finite field]]s.<ref>{{citation | last1 = Davidoff | first1 = Giuliana | author1-link = Giuliana Davidoff | last2 = Sarnak | first2 = Peter | author2-link = Peter Sarnak | last3 = Valette | first3 = Alain | doi = 10.1017/CBO9780511615825 | isbn = 0-521-82426-5 | mr = 1989434 | publisher = Cambridge University Press, Cambridge | series = London Mathematical Society Student Texts | title = Elementary number theory, group theory, and Ramanujan graphs |title-link=Elementary Number Theory, Group Theory and Ramanujan Graphs| volume = 55 | year = 2003}}</ref> These remarkable ''[[Ramanujan graphs]]'' also have large [[expander graph|expansion coefficient]].