2
$\begingroup$

Let $G = (V, E)$ a critical graph; i.e. a graph s.t. for any subgraph $H \subseteq G$ we have $\chi(H) < \chi(G)$. I was requested to prove that $\chi(G) \leq \delta + 1$, where $\delta$ is the degree of the vertex (or vertices) of lesser degree in $G$.

I presume that I need to relate a sub-graph $H$ that involves the vertex (or vertices) of $G$ whose degree is $\delta$ and somehow prove that the chromatic number of this subgraph is $\delta$. Then the property follows from the fact that $G$ is critical. However, I was unable to construct such subgraph.

Am I taking the wrong approach? Any hints/suggestions are appreciated.

$\endgroup$
1
  • $\begingroup$ Suppose by contradiction that there exist $G$ a critical graph with $\chi(G) > \delta + 1$. Show that you can find a coloring with less than $\chi(G)$ colors. $\endgroup$
    – caduk
    Commented Mar 21 at 16:52

1 Answer 1

Reset to default
1
$\begingroup$

Let there be a vertex of degree less than $\chi(G)-1$. Remove it and its edges. Since $G$ is critical, the rest can be coloured with $\chi(G)-1$ colours. Now put the removed vertex back. Its degree is less than the number of used colours, so we can colour it with one of the already used colours. Contradiction with the definition of $\chi(G)$.

$\endgroup$
3
  • $\begingroup$ We have no reason to assume there is a vertex of degree less than $\chi(G) - 1$. What am I missing? $\endgroup$
    – lafinur
    Commented Mar 25 at 0:00
  • $\begingroup$ @lafinur We want to prove that $\chi(G)\le\delta+1$. We go for the contradiction and assume the opposite: that $\chi(G)>\delta+1$. Or $\delta<\chi(G)-1$. So the vertex of the smallest degree has degree less than $\chi(G)-1$. We will then arrive to the contradiction. $\endgroup$
    – Aig
    Commented Mar 25 at 0:08
  • 1
    $\begingroup$ I see. Thank you! $\endgroup$
    – lafinur
    Commented Mar 25 at 0:43

You must log in to answer this question.

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