 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2007/a/4/b/solution

An even cycle is bipartite and has chromatic number two. An odd cycle has chromatic number three. The extremal-density theorem therefore gives

n \to \infty lim \frac{ex ( n ; C _{k} )}{( 2 n )} = {0, 1/2, k even, k odd .

For odd cycles the complete balanced bipartite graph also exhibits the matching asymptotic lower density one half.

 New to topics? Read the docs here!