StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q28E

Expert-verifiedFound in: Page 734

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\)

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.

**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)\) **

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\)

94% of StudySmarter users get better grades.

Sign up for free