I try to prove the following statement: "If every subgraph of an undirected graph has at least one vertex with degree at most $k$, then the graph can be colored with at most $k+1$ colors"
My first idea was to apply the statement "Each graph with $n$ vertices and maximum vertex degree $\leq k$ is $(k + 1)$-colorable." Which I proved by induction. But I just don't see how the proof could work.
Assume $G$ is a minimal counter-example to the claim. Then $G$ itself has a vertex of degree $\le k$, and $G-v$ also fulfils the subgraph-degree-condition of the claim. By minimality of $G$, $G-v$ is $(k+1)$-colourable, and we can assign a colour not used inits $\le k$ neigbours to $v$.