Skip to main content
3 of 8
added 253 characters in body
Jon Noel
  • 761
  • 7
  • 11

A $k$-core of a graph is a connected subgraph in which every vertex has degree at least $k$. Your set $S_k$ is the union of the vertex sets of the $k$-cores of the graph.

https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#k-Cores

Similar to what Gerhard suggested, you can find the set $S_k$ by starting with $V(G)$ and deleting every vertex of degree less than $k$ until there are none left.

With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.

Jon Noel
  • 761
  • 7
  • 11