# How would I prove that the algorithm to find the k-cores graph, produces a maximum size of vertices?

I came across this simple algorithm for finding a k-core of a graph, but every paper I read gives this notion of being maximal without proof, and I'm wondering how I might prove it.

So a k-core of a graph $$G$$ is a maximal induced subgraph $$H \subseteq G$$, such that all the degree of the vertices in $$H$$ are at least $$k$$.

The algorithm idea is to recursively delete vertices with degree $$< k$$, until we don't delete any further vertices.

Intuitively, it makes sense why this is a maximal subgraph. But I'm unsure how one would prove that this algorithm produces the maximum number of vertices for such a subgraph $$H$$ with $$\geq k$$ degree on every vertex.

I was considering, by contradiction. Suppose if it is not maximal, then we have some other vertex that belongs in the subgraph. But we initially removed this vertex because it either had an original degree $$ or its neighbors had degree $$ at some point in the algorithm. If we return its neighbors to satisfy it, its neighbors also have less than $$k$$, so we would continue until we realize we cannot satisfy the original vertices removed because they originally had $$.

• Prove inductively that every vertex removed from the graph cannot possibly belong to any subgraph with minimum degree at least $k$. Commented Apr 26, 2022 at 17:55
• @YuvalFilmus Hmm, I'm not sure what the predicate would be. I think I have another proof idea though. I know that the output $H$ is a $\subseteq C_k(G)$, where $C_k(G)$ is the optimal. For an arbitrary $v \in C_k(G)$, $v$ has $k$ neighbors in $C_k(G)$. None of its neighbors will be removed on the first iteration because they have degree $\geq k$. If none are removed on the $n^{th}$ iteration, none will be removed on the $n+1^{th}$ iteration. Therefore, we know that $v \in H$. So $H = C_{k}(G)$. Commented Apr 26, 2022 at 18:26
• The induction is on the number of vertices removed, or on the number of steps in the algorithm. Commented Apr 26, 2022 at 18:27
• @YuvalFilmus Ah I think I understand what you mean. In that case, is the induction hypothesis to say that the remaining graph (after removal of some node because it has degree $< k$), that the remaining graph $G'$'s k-core is the same as the k-core of the original graph $G$? Commented Apr 26, 2022 at 18:31
• This is one option. The other option is to show that if you remove a vertex, then it cannot belong to any subgraph with minimum degree at least $k$. Commented Apr 26, 2022 at 18:35