Let G be a graph with at least two vertices Prove that omega

Let G be a graph with at least two vertices. Prove that omega (G) > = 2. alpha(G) > = 2 or

Solution

The graph in a clique with n vertices where(n>=2), in a clique any two vertices are adjacent to each other

while having clique(4), it will be attached to every other three vertices so we need minimum of two colors. Let us prove it by mathematical induction ase

Case 1: Base case (n=2)

If n=2, then the two vertices are connected to each other so we can\'t give the same color to both of them, hence in that case minimum colors required are 2

So, the base case holds true

Case 2: General Case (n>2)

So assuming a clique has n vertices we need n colors, so the clique number cannot be greater than the chromatic number

Since we know that we can\'t color the adjacent vertex with the same color, hence it is always greater than alpha(G) which is n

Hence alpha(G) >=2 (equal to 2 in the case of n=2 (only two vertices))