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$
2
  • $\begingroup$ Stop trying to hide your own question! Your behavior has been reported. $\endgroup$
    – Giuseppe Negro
    Oct 13, 2018 at 15:46
  • $\begingroup$ That sounds like a very convoluted way of saying "the maximum degree of an undirected Graph is $\le k$ " $\endgroup$
    – DanielV
    Aug 30, 2021 at 11:46

1 Answer 1

Reset to default
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$
2
  • 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, 2018 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, 2018 at 1:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .