In this page, let us prove that the chromatic number of a complete graph with n vertices is n.

Before proving this, let us recall the definition of the chromatic number of a graph.

Chromatic Number of a Graph

Definition: The chromatic number of a graph G, denoted by $\chi(G)$, is the minimum number of colours needed to colour the vertices of the graph such that no two adjacent vertices share the same colour.

Chromatic Number of a Complete Graph

Theorem: Show that the chromatic number of a complete graph with n vertices is n.

Proof:

A complete graph is a graph where each pair of distinct vertices is connected by a unique edge. So in such case, each vertex is adjacent to all other n-1 vertices. Since no two vertices can share the same colour, so the minimum number of colours needed to colour all the vertices is n.

Hence, it follows that the chromatic number of a complete graph with n vertices is n.

Also Study:

1. Degree of a Vertex in Graph: Definition, Examples, Handshaking Theorem
2. Simple Graph has Two Vertices of Same Degree: proof
3. Prove that a tree with n vertices has (n-1) edges
4. Simple Graph with n Vertices and k Components have at most (n-k)(n-k+1)/2 Edges