• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q28E

Expert-verified
Found in: Page 734

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# What can be said about the chromatic number of a graph that has $${K_n}$$as a subgraph?

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

See the step by step solution

## Step 1: 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.

## Step 2: 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)$$

## Step 3: 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$$