The Wikipedia definition of the degeneracy of a graph.

graph theory

I'm trying to understand Wikipedia's definition of "Degeneracy (graph theory)" which says:

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges.

Degeneracy – Wikipedia

But then I look at the example and it does not make sense to me. Here is the graphic:

2-core

Now, from what I understand, a subgraph can be any subset of vertices and edges from the original graph. If so, one vertex can be a subgraph. If so, the 2-degenerate graph has many single vertices (aka subgraphs) that touch more than 2 edges.

I am sure I am missing something, but I don't know what it is.

Best Answer

Each edge of a subgraph must have two vertices. (These vertices need to be in the subgraph.) That is, a single vertex with one or more edges from it, but with the edges not connected to other vertices of the subgraph at their "other ends", is not considered a subgraph.

Related Question