Ask Question
1 September, 03:36

Prove that if a graph with n vertices has chromatic number n, then the graph has

n (n-1) edges.

+1
Answers (1)
  1. 1 September, 05:52
    0
    We are given a graph with n vertices whose chromatic number is n.

    That implies we need at least n colors to color the graph, such that no two adjacent vertices will get the same color.

    As the chromatic number is n, all vertices will get a distinct color in a valid coloring.

    Now we can conclude that there is an edge between every pair of vertices,

    otherwise, we can assign the same color to two non-adjacent vertices, and we could have a valid coloring with some k colors, for k
    So the chromatic number would be k.

    But as it's n, there is an edge between every pair of vertices, and it's a complete graph, so the total number of edges=n (n-1).
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “Prove that if a graph with n vertices has chromatic number n, then the graph has n (n-1) edges. ...” in 📙 Mathematics if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers