How do I prove that the vertex chromatic number of a subgraph is less than that of the original graph? Say I have a graph with chromatic number $k$. How do I prove that the chromatic number any subgraph is less than $k$?
[Math] How to prove that the vertex chromatic number of a subgraph is less than that of the original graph
coloringgraph theory
Best Answer
Let C be a k-coloring of the graph. You can reduce it to a vertex coloring of a subgraph (by simply using the same colors). So the chromatic number of the subgraph is less than or equal to k.