Content deleted Content added
Line 59:
A 1959 paper of Erdős (see reference cited below) addressed the following problem in [[graph theory]]: given positive integers {{mvar|g}} and {{mvar|k}}, does there exist a graph {{mvar|G}} containing only [[cycle (graph theory)|cycles]] of length at least {{mvar|g}}, such that the [[chromatic number]] of {{mvar|G}} is at least {{mvar|k}}?
It can be shown that such a graph exists for any {{mvar|g}} and {{mvar|k}}, and the proof is reasonably simple. Let {{mvar|n}} be very large and consider a random graph {{mvar|G}} on {{mvar|n}} vertices, where every edge in {{mvar|G}} exists with probability {{math|''p'' {{=}} ''n''<sup>1/''g''−1</sup>}}. We show that with positive probability, {{mvar|
:'''Property 1.''' {{mvar|G}} contains at most {{math|''n''/2}} cycles of length less than {{mvar|g}}.
| |||