Question

What can be said about the chromatic number of a graph that has \({K_n}\)as a subgraph?

Short answer

\(\chi \left( G \right) \ge n\)

Step-by-step solution

Note the given data

Given \({K_n}\)is a subgraph of the given graph G.

We need to find the chromatic number of the given graph under the given conditions.

Definition

The chromatic number of a graph is the smallest number of colors that can be used in an edge coloring of the graph. The edge chromatic number of a graph is denoted by \(\chi \left( G \right)\)

Calculation

As n colours are absolutely necessary to color \({K_n}\), it follows that the chromatic number \(\chi \left( G \right)\) must be at least n, as the number of vertices of G is at least n (since the vertices of \({K_n}\) is a subset of the vertices of G)

So\(\chi \left( G \right) \ge n\)

Hence solution is \(\chi \left( G \right) \ge n\)