What is the difference between a $k$-degenerate graph and a graph with max vertex degree $k$?

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$?

• Didn't you mean the minimum degree of $G$, $\delta(G)$? – 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.
• 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$" – M.K. Feb 9 '14 at 13:31