necessary and sufficient chromatic number $\chi$ of a graph Which chromatic number $\chi(G)$ (vertex coloring number) is necessary and which is sufficient for the following undirected Graph:
$G = (V, E)$ with 
$V = \{1,2,3,4,5,6,7\}$ and 
$E = \{\{1,2\}, \{1,6\}, \{2,3\}, \{2,4\}, \{3, 5\}, \{3,7\}, \{4,6\}, \{5,7\}, \{6,7\}\}$
I know that the Graph $G$ can be colored with at least 3 colors without conflicts, for instance:
Vertices 1, 3, 4 (red)
Vertices 2, 5, 6 (green)
Vertex 7 (blue)
So $\chi(G) = 3 $ is the necessary chromatic number or is $\chi(G) \le 3$ is necessary, since $1$ and $2$ are necessary for $3$?
A different coloring could be, that each vertex has a unique color.
In this case $\chi(G) = 7$ would be the sufficient chromatic number since there are $7$ vertices. Or is $\chi(G) \le 7$ the sufficient number, since the graph could be colored also with $4, 5$ or $6$ colors?
Could anyone tell me please, what is wrong and what is right?
Thanks
 A: Part of your confusion seems to be about terminology and notation, so let me address that.
We can say "$k$ colors are necessary to (properly) color $G$": this means you cannot color $G$ with fewer than $k$ colors. For clarity, you can say "At least $k$ colors are necessary to color $G$", but this means exactly the same thing. In your particular example, we can make statements such as:


*

*$1$ color is necessary, because $G$ has vertices, and they need to be given colors.

*$2$ colors are necessary, because vertices $1$ and $2$ are adjacent, so just coloring them requires two different colors.

*$3$ colors are necessary, because any two of the vertices $3$, $5$, and $7$ are adjacent, so coloring these three vertices requires three different colors.


(In general, there could be subtler reasons why $k$ colors are necessary, but that's all we've got in this example.)
We can say "$k$ colors are sufficient to (properly) color $G$": this means that there exists a coloring with $k$ colors. In your example, we can say:


*

*$3$ colors are sufficient, because there is a coloring of $G$ with three colors: color vertices $1,3,4$ red, vertices $2,5,6$ green, and vertex $7$ blue.

*$4$ colors are sufficient, because the above coloring is also a coloring of $G$ with the four colors red, green, blue and yellow. It happens never to use yellow.

*The same argument shows why larger number of colors are sufficient, too.

*Another reason why $7$ colors are sufficient is that we can give every vertex its own color. (In general, for an $n$-vertex graph, $n$ colors are always sufficient.)


But there is no such thing as the "necessary chromatic number" or "sufficient chromatic number" of a graph. The chromatic number $\chi(G)$ of a graph $G$ always refers to the least number of colors we can use to color $G$, so in this example $\chi(G)=3$. It's always exactly one number (even when we don't know it yet, and even if we're thinking about suboptimal colorings that use a different number of colors). To prove that $\chi(G)=3$, we need to show that $3$ colors are sufficient (there is a $3$-coloring of $G$) and that $3$ colors are necessary (we can't color $G$ with fewer colors).
The statement "$k$ colors are necessary to color $G$" is equivalent to saying that $\chi(G) \ge k$, and the statement "$k$ colors are sufficient to color $G$" is equivalent to saying that $\chi(G) \le k$. But that's just a way of putting a sentence into mathematical notation.
