Prove that if a graph with n vertices has chromatic number n, then the graph has
n(n-1) edges.

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<n.

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

15

step-by-step explanation: