<p>See <a href="http://en.wikipedia.org/wiki/Degeneracy_(graph_theory" rel="nofollow">http://en.wikipedia.org/wiki/Degeneracy_(graph_theory</a>)</p>

<p>Essentially, a degeneracy ordering is an ordering on the vertices that you get from repeatedly removing a vertex of minimum degree in the remaining subgraph. The degeneracy of the graph is the smallest number d such that every vertex has at most d neighbors that are later than it in the ordering. Among all possible orderings, the degeneracy orderings minimize this number.</p>

CC BY-SA 3.0
2011-05-08T07:13:26.880Z
2011-05-08T07:13:26.880Z
David Eppstein
<p>There is a step in <a href="http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm" rel="nofollow noreferrer">Bron–Kerbosch algorithm</a></p>

<p>for each vertex v in a degeneracy ordering of G:</p>

<p>what is "a degeneracy ordering of G"?  For example what is vertex in a degeneracy ordering  in </p>

<p>this graph </p>

<p><img src="https://upload.wikimedia.org/wikipedia/commons/5/5b/6n-graf.svg" width="300" height="200"></p>

CC BY-SA 3.0
2011-05-08T07:44:49.287Z
This is a site for research-level questions in theoretical computer science.  The answer to your question can be found in a link from the wikilink of your post.
RJK
<graph-theory><co.combinatorics><terminology>
vertex in a degeneracy ordering of a undirected graph
icn
# vertex in a degeneracy ordering of a undirected graph

(Asked by: username_0 on 2011-05-08)

There is a step in [Bron–Kerbosch algorithm](http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm)

for each vertex v in a degeneracy ordering of G:

what is "a degeneracy ordering of G"? For example what is vertex in a degeneracy ordering in

this graph

![](https://upload.wikimedia.org/wikipedia/commons/5/5b/6n-graf.svg)

**Tags:** graph-theory, co.combinatorics, terminology
> **Comments:**
> **username_1**: This is a site for research-level questions in theoretical computer science.  The answer to your question can be found in a link from the wikilink of your post.  

---

## 1 answers

### Answer by username_2 on 2011-05-08. Score: 2

See <http://en.wikipedia.org/wiki/Degeneracy_(graph_theory>)

Essentially, a degeneracy ordering is an ordering on the vertices that you get from repeatedly removing a vertex of minimum degree in the remaining subgraph. The degeneracy of the graph is the smallest number d such that every vertex has at most d neighbors that are later than it in the ordering. Among all possible orderings, the degeneracy orderings minimize this number.


---

