1
$\begingroup$

I'm in a discrete math course and was trying to prove the following theorem:

A graph G with $\Delta(G) = k$ ($\Delta(G)$ is the max vertex degree) is $(k+1)-$coloreable.

I've tried my own, and I've read the answers in here, here and this but I still have a big doubt using an induction proof as shown in 2.

In the induction step, when we delete a vertex v of the graph $G$ with $\Delta(G) = k$: What garantees me that once the vertex is deleted, $\Delta(G)$ is stil k? As they show that $\Delta(G') = k$, what garantees that?

PD: pardon my english, I'm not native speaker.

$\endgroup$
2
  • $\begingroup$ Are you dead set on using induction? The easiest proof of this that I could think of would be to use the greedy coloring algorithm: en.wikipedia.org/wiki/Greedy_coloring $\endgroup$
    – Paralyzed_by_Time
    May 30, 2020 at 22:05
  • $\begingroup$ @Paralyzed_by_Time yes I though using it, but I'm requested on using induction. I've tought on using two scenarios: one in which the vertex I delete is not adjacent to the vertex with highest degree, and the other in which are two vertex of max degree adjacent and I delete one of them. Still, I'm wondering if there's a straight formulation, or why is the proposed in the previous questions valid and not dealing with this issue $\endgroup$
    – dante95
    May 30, 2020 at 22:17

1 Answer 1

Reset to default
3
$\begingroup$

It’s entirely possible that after $v$ is removed, the maximum degree of the resulting graph $H$ is less than $k$. It doesn’t matter: the result being proved at that link is that if $\Delta(G)\color{red}{\le}k$, then $G$ is $k$-colorable. We assumed that $\Delta(G)\le k$, and removing a vertex cannot increase the maximum degree, so $\Delta(H)\le k$, and we can apply the induction hypothesis.

$\endgroup$
2
  • $\begingroup$ Thank U for that!!! I was thinking that, $H$ should be $\Delta(H) \leq k $ instead $\Delta(H) = k $ and that would make more sense to me. I can see the demonstration sense, but the = was bothering me. $\endgroup$
    – dante95
    May 30, 2020 at 22:20
  • $\begingroup$ @dante95: You’re welcome! $\endgroup$
    – Brian M. Scott
    May 30, 2020 at 22:24

You must log in to answer this question.

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