# 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.

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.

• Stop trying to hide your own question! Your behavior has been reported. – Giuseppe Negro Oct 13 '18 at 15:46

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$$.
• @quinostic "Every subgraph" includes the whole graph itself. The hypothesis "every subgraph has at least one vertex with degree at most $k$" tells you that $G$ has at least one vertex with degree at most $k$. Choose such a vertex and call it $v$. Then $v$ has at most $k$ neighbors because, if it had more than $k$ neighbors, then it would have at least $k+1$ neighbors, and $k+1$ edges joining $v$ to those neighbors, which would make $v$ have degree $\ge k+1$, contradicting the assumption that the degree of $v$ is at most $k$. Is that detailed enough? – bof Oct 13 '18 at 1:12
• @quinostic Every subgraph of $G$ has a vertex of degree at most $k$. Since $G-v$ is a subgraph of $G$, every subgraph of $G-v$ is also a subgraph of $G$, and therefore has a vertex of degree at most $k$. – bof Oct 13 '18 at 1:19