Define chromatic number. How does Kruskal's algorithm find Minimum Spanning Tree?

Chromatic number χ(G) of a graph G is the smallest number of colours needed to colour its vertices so that no two adjacent vertices have the same colour. For example, χ = 2 for any bipartite graph (with at least one edge), χ(Kₙ) = n for the complete graph, and a cycle with an odd number of vertices needs 3 colours.

Kruskal's algorithm for a minimum spanning tree

A minimum spanning tree (MST) of a connected weighted graph is a spanning tree whose total edge weight is as small as possible. Kruskal's algorithm builds it greedily:

1. Sort all edges in increasing order of weight.
2. Start with a forest where every vertex is its own tree, and an empty edge set T.
3. Take the next smallest edge. If it joins two different trees (so it does not form a cycle with the edges already in T), add it to T. Otherwise discard it.
4. Repeat until T has n − 1 edges (n = number of vertices).

Example: vertices A, B, C, D with edges AB = 1, BC = 2, AC = 3, CD = 4, BD = 5.

MST = {AB, BC, CD}, with total weight 1 + 2 + 4 = 7.

With a union-find structure to detect cycles, Kruskal's algorithm runs in O(E log E) time.