# degeneracy -- Computes the degeneracy of a graph

## Synopsis

• Usage:
d = degeneracy G
• Inputs:
• G, an instance of the type Graph,
• Outputs:

## Description

The degeneracy of a graph is the maximum degree of all vertices in any subgraph of G. This is essentially equivalent to the coloring number of G, which is the least number k such that there exists an ordering of the vertices of G in which each vertex has less than k neighbors earlier in the ordering. The coloring number is equal to the degeneracy plus one.

 i1 : G = completeGraph 10; i2 : degeneracy G o2 = 9

## Ways to use degeneracy :

• "degeneracy(Graph)"

## For the programmer

The object degeneracy is .