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](http://en.wikipedia.org/wiki/Tur%25C3%25A1n%27s_theorem), 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.



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

> 
> $$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.


