# Find the exact maximum number of edges for a $$k$$-critical graph on n vertices

A graph is said to be edge critical if the deletion of any edge decreases the chromatic number by $$1$$. Analogously, a graph is said to be vertex critical if the deletion of any vertex decreases the chromatic number by $$1$$. Here we use the convention that a critical graph means an edge critical graph.

A critical graph with chromatic number $$k$$ is said to be a $$k$$-critical graph. Similarly, a vertex critical graph with chromatic number $$k$$ is said to be a $$k$$-vertex-critical graph.

# Problem (1949)

What is the largest number $$m$$, denoted by $$f(n,k)$$, such that there is a $$k$$-critical graph on $$n$$ vertices and $$m$$ edges? In particular, determine $\lim_{n \rightarrow \infty} \frac{f(n,k)}{n^2} = c_k.$

Bibliography
1 P. Erdös, Problems and results on chromatic numbers in finite and infinite graphs, Graph theory with applications to algorithms and computer science (Kalamazoo, MI, 1984), Wiley-Intersci. Publ., 201-213, Wiley, New York, 1985.