Question

Find the chromatic number of the given graph.

Short answer

The Chromatic number of the given graph is \(4\).

Step-by-step solution

Given data in the question.

In the question, a graph is given

Definition to be used.

According to the definition of chromatic number of a graph, the chromatic number of a graph is the least number of colors needed to color a graph so that no two adjacent vertices are assigned the same color.

Find the chromatic number of the given graph.

Since, the vertex \(a\) is connected directly to the vertices \(b,h\) and \(i\) but not \(c\). So, the color of vertices \(a\) and \(c\) can be same.

Similarly,

The vertex \(d\) is connected directly to the vertex \(c\) and \(i\) but not \(b\)and \(h\). So, the color of vertices \(d\) and \(b\) can be same.

The vertex \(e\) is connected directly to the vertex \(d\) and \(i\) but not \(c\)and \(h\). So, the color of vertices \(c\) and \(e\) can be same.

The vertex \(g\) is connected directly to the vertex \(a,c,d,f\) and \(h\) but not \(e\)and \(i\). So, the color of vertices \(g\) and \(i\) can be same.

The vertex \(f\) is connected directly to the vertex \(c,e\) and \(g\) but not to any other vertices. So, the color of vertices \(f\) and \(a\) can be same.

Therefore,

Vertex	Color
a	Red
b	Blue
c	Red
d	Blue
e	Red
f	Blue
g	Orange
h	Green
i	Orange

Hence, \(4\) different colors are used to color the given graph. So, the chromatic number of the given graph is \(4\).