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

User Asalle
by
5.9k points

1 Answer

3 votes

Answer:

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

User EkcenierK
by
5.8k points