# randomly sample a degeneracy ordering

Given an undirected graph $$G$$, the $$k$$-core of $$G$$ is defined as the maximal subgraph such that each vertex has at least $$k$$ neighbors in the subgraph. The cores of $$G$$ can be computed by the following algorithm, which computes the $$k$$-core by iteratively removing vertices with degree $$< k$$.

1: $$k \leftarrow 1$$;

2: while $$G$$ is not empty:

3: $$\$$ $$\$$ while there is a vertex $$v$$ with degree $$< k$$:

4: $$\$$ $$\$$ $$\$$ $$\$$ decrease by $$1$$ the degree of the neighbors of $$v$$ in $$G$$;

5: $$\$$ $$\$$ $$\$$ $$\$$ remove $$v$$ from $$G$$;

6: $$\$$ $$\$$ $$k \leftarrow k + 1$$;

An order that the vertices are removed in line 5 is called a degeneracy order. There can be multiple degeneracy orders for $$G$$ due to the tie in line 3.

Question. I want to uniformly sample a degeneracy ordering for $$G$$. I wonder if this is a known question in the community. I have googled it but found nothing. Is there an efficient algorithm for this task?