0
$\begingroup$

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.

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

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

$\endgroup$
  • 1
    $\begingroup$ @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? $\endgroup$ – bof Oct 13 '18 at 1:12
  • 1
    $\begingroup$ @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$. $\endgroup$ – bof Oct 13 '18 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.