Maximum number of edges $f(n,k)$ in a graph on $n$ vertices with no $k$-core?

Question

The $k$-core of a finite graph is defined as follows. Delete all vertices of degree $< k$ and repeat until there are no such vertices left. If there is a nonempty subgraph remaining, necessarily of minimum degree $\ge k$, we call this graph the $k$-core. If the deletion process results in removing all vertices, we say that the graph has no $k$-core.

Let $f(n,k)$ denote the maximum number of edges in a simple graph on $n$ vertices with no $k$-core. For example, if $f(n,2)=n-1$ for every $n$, since $n$ edges are sufficient (and necessary) to guarantee the existence of a cycle.

What about $k \ge 3$? Maybe a formula is too much to hope for, so for fixed $k$ what are the asymptotics of $f(n,k)$ as $n \to \infty$?

I suspect this kind of question has been studied, so any references would be appreciated. It is very similar in flavor to questions in "classical" extremal graph theory, where one tries to maximize the number of edges in a graph on $n$ vertices with no $H$-subgraph, where $H$ is a fixed graph. This question fits in a more general setting where $H$ ranges over an infinite family of possible subgraphs.

Answer 1

$$f(n,k)= (n-k)(k-1)+\frac{k(k-1)}{2}, \; \mathrm{for} \; n \geq k, $$ $$f(n,k) = \frac{n(n-1)}{2}, \; \mathrm{for} \; n \leq k. $$

Proof: Every graph with no $k$-core on $n$ vertices contains a vertex of degree $\leq k-1$ which one can delete, obtaining a graph with no $k$-core. Thus $$f(n,k) \leq f(n-1,k) + k-1.$$

The formula now follows by induction. In the base case $n \leq k$ the formula gives the number of edges in the complete graph.

For an example that the bound can be achieved, let $G$ be a graph with $V(G) = \{1,2, \ldots, n \}$ and let the vertices $i$ and $j$ be adjacent if and only if $|i-j| < k$. It is easy to check that $G$ has no $k$-core and has the right number of edges.

Answer 2

If I'm not confused, I believe the graphs you are searching for (with a $k-1$ core but no $k$-core, and adding any edge creates a $k$-core) are also called "maximal $(k-1)$-degenerate graphs," see e.g. the wikipedia article on degeneracy.

The paper "k-degenerate graphs" of Lick and White proves the following:

Corollary 1: Let $G$ be a maximal $k$-degenerate graph with $p$ points, $p\geq k$. Then $G$ has $kp-\binom{k+1}{2}$ [edges].