Degeneracy number of a ring graph

318 Views Asked by At

The definition of $k-$ degeneracy is not clear to me. Could someone please explain how is degeneracy number different from maximum degree $\Delta G$ of the graph $G$? And second question is, does a ring graph has $k=2$?

1

There are 1 best solutions below

6
On BEST ANSWER

A tree has leaves, and therefore is $1$-degenerate, while the max degree is unlimited.

If by the ring graph you mean a cycle, then every subgraph of the cycle only has vertices of the degree $1$ and $2$, thus the cycle is $2$-degenerate.