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$?
$\endgroup$ 11 Answer
$\begingroup$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):
$\endgroup$ 1More 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.
