Independence number of graph below

320 Views Asked by At

I’m trying to find the independence number of the graph below: enter image description here

I’ve been told that the independence number is 3 but I’m pretty certain it’s two since the chromatic number of the graph is 3 and the maximal number of vertices with one colour in any proper 3-colouring is 2. I can’t see why I would be wrong.

1

There are 1 best solutions below

1
On BEST ANSWER

The independence number of this graph is indeed $3$. The three vertices of the largest triangle forms the corresponding set of independent vertices. There is a proper coloring of this graph in which these three vertices can be assigned the same color.