Question

Show that the number of vertices in a simple graph is less than or equal to the product of the independence number and the chromatic number of the graph.

Short answer

Most of the ki vertices are proving the required thing.

Step-by-step solution

Introduction

The chromatic number of a graph is the smallest number of colours needed to colour the vertices of so that no two adjacent vertices share the same colour i.e., the smallest value of possible to obtain a k-colouring.

Show that  

To prove this, we first assume that we have a graph G which is coloured with k colours and has independence number i .

Then, consequently each colour class will be an independent set. It is also an

obvious point that each colour class has no more than i elements.

Thus, there are at most a total of ki vertices which proves the required thing.