A $k$-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most $k$. But a subgraph $H$ of a graph $G$ can be equal to the full graph $G$, therefore there will always be one subgraph containing the vertex with the maximum degree $k$.

Did I misunderstand some definition? Could you give me some example of a graph with maximum vertex degree $k$, but is $l$-degenerate, where $l < k$?

  • $\begingroup$ Didn't you mean the minimum degree of $G$, $\delta(G)$? $\endgroup$ – Ragnar Feb 9 '14 at 10:42

A $k$-degenerate graph needs only to have (at least) one vertex of degree at most $k$ in every subgraph, while the maximum degree is the largest degree of all vertices, which is completely unrelated. If you take the graph with $101$ vertices where one vertex is connected to all others but none of those vertices are connected, we have $\Delta(G)=100$, but every subgraph of $G$ contains a vertex of degree $1$, so $G$ is $1$-degenerate.

Quote from Wikipedia (at the examples section):

More strongly, the degeneracy of a graph equals its maximum vertex degree if and only if at least one of the connected components of the graph is regular of maximum degree. For all other graphs, the degeneracy is strictly less than the maximum degree.

  • 1
    $\begingroup$ Oh, now I get it. I thought "every subgraph has a vertex of degree at most k" means "$\Delta(H) \leq k$ for each subgraph H" which didn't make sense. It's supposed to be "every subgraph has at least one vertex that has degree $\leq k$" $\endgroup$ – M.K. Feb 9 '14 at 13:31

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.