= Why the 2-core is unique
Suppose $T$ is any <vertex set> whose <induced subgraph> has every <degree of a vertex> at least two. No <vertex> of $T$ can be the first one deleted from $T$: before such a deletion it still has its two <graph neighbours> within $T$, contradicting eligibility for deletion. Consequently every qualifying $T$ survives every legal deletion sequence. Once deletion stops, its remainder $R$ itself qualifies, because every surviving <vertex> has at least two surviving <graph neighbours>. Therefore $T\subseteq R$ for every qualifying $T$: $G[R]$ is the unique maximum and the final remainder is independent of deletion order. The intermediate <FIFO queues> and deletion orders can differ.
There is also a direct existence argument. If $A$ and $B$ qualify, then $A\cup B$ qualifies: each <vertex> retains at least the two <graph neighbours> it already had in $A$ or in $B$. Taking the <union> of all qualifying <vertex sets> produces the maximum. This rules out a collection of competing, incomparable inclusion-maximal answers. It also explains why restricting the search to connected <subgraphs> would change the question.
Back to article page
