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:


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.


1 Answer 1


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.

  • 1
    $\begingroup$ Ah yes, in the context of a subgraph, an edge does not exist unless connected on both ends by vertices. $\endgroup$ Nov 21, 2018 at 18:13
  • $\begingroup$ However, if I choose the 4th, 6th, and 10th nodes as the subgraph, the 4th vertices is touching 3 edges whose other ends are connected to vertices. So this is more than a 2-degenerate graph? $\endgroup$ Nov 21, 2018 at 18:25
  • $\begingroup$ If you only choose the 4,6,10 vertices and no edges, that subgraph has each vertex degree 0. If you choose for your subgraph vertices 4,6,10 and edges (4,6), (4,10), (6,10) then each of vertices 4,6,10 has degree 2 in the subgraph. $\endgroup$
    – coffeemath
    Nov 21, 2018 at 18:33
  • $\begingroup$ Also wiki definition only says each subgaph has a (i.e. at least one) vertex of degree $d \le k$ to be called $k$-degenerate. It doesn't matter if the subgraph has some other vertices of degree more than $k,$ only that at least one vertex in the subgraph has degree $d \le k.$ $\endgroup$
    – coffeemath
    Nov 21, 2018 at 18:38
  • $\begingroup$ I see, I should have included edges too. Anyway I think I get it now. I actually thought it meant no vertex in a subgroup can have more than two edges connected to another vertex. $\endgroup$ Nov 21, 2018 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.