Ask Question
3 November, 13:37

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

n (n-1) edges.

+1
Answers (1)
  1. 3 November, 14:01
    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?
Find 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 you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers