-2
$\begingroup$

I need this proof:

Let $G$ be a graph such that $\chi (H) <\chi (G)$ for every subgraph $H$ of $G$. A graph is called $k$-critical, if in addition $\chi (G) = k$. Prove that $\chi (G) ≤ \delta + 1$.

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
5
$\begingroup$

Let $n= \chi(G)$ and suppose there is $v\in V(G)$ such that $d(v) < \chi(G)-1$. Then you can color $G\setminus \{v\}$ with $n-1$ colors (because of criticalness). Since $v$ has less than $n-1$ neighbors, those neighbors use up less than $n-1$ colors; let $k\in \{1,\ldots,n-1\}$ be the color that is not used. Then color $v$ with color $k$ and you colored $G$ with $n-1$ colors, contradicting that $n=\chi(G)$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Perfect!!! This was the proof, I understand now perfectly. Thanks $\endgroup$
    – dantopa
    Commented Mar 31, 2017 at 20:46
  • 1
    $\begingroup$ Sorry it's my first time on the site. I think it's accepted now $\endgroup$
    – dantopa
    Commented Apr 1, 2017 at 13:20

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