# Math Help - graph theory, chromatic number relation

1. ## graph theory, chromatic number relation

Let G be a simple graph with v vertices and every vertex of degree d. Show that $\chi (G) \geq \frac{v}{(v-d)}$

where $\chi (G)$ is the chromatic number, the least k for which the graph G is k-colourable.

2. Originally Posted by Jason Bourne
Let G be a simple graph with v vertices and every vertex of degree d. Show that $\chi (G) \geq \frac{v}{(v-d)}$

where $\chi (G)$ is the chromatic number, the least k for which the graph G is k-colourable.
Remark: let $V$ be the set of verices of $G.$ if $A \subseteq V$ has this property that no two vertices in $A$ are adjacent, then $|A| \leq v-d.$ this is because if $|A| \geq v-d+1,$ then $|V-A| \leq d-1$ and so

a vertex in $A$ can be adjacent to at most $d-1$ vertices, which contradicts $d$ regularity of $G.$

now label the colors with $1, 2, \cdots , \chi(G),$ and for any $1 \leq k \leq \chi(G)$ let $A_k$ be the set of all vertices in $V$ colored $k.$ then clearly $\bigcup_{k=1}^{\chi(G)} A_k=V$ and for any $i \neq j: \ A_i \cap A_j = \emptyset.$ also by the above
remark $|A_k| \leq v-d,$ for all $1 \leq k \leq \chi(G).$ therefore: $v=|V|=\sum_{k=1}^{\chi(G)} |A_k| \leq (v-d) \chi(G).$ Q.E.D.

3. there's a lower bound for the chromatic number of any simple graph, which generalizes your problem and the proof is just a simple modification of the proof i gave you:

let $G$ be any simple graph, $V$ the set of vertices of $G,$ and $W$ the largest subset of $V$ with this property that no two vertices in $W$ are adjacent. then: $\chi(G) \geq \frac{|V|}{|W|}.$