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$?
Best Answer
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):