Gallai–Hasse–Roy–Vitaver theorem

The Gallai–Hasse–Roy–Vitaver theorem is a result in graph theory that relates two important concepts: the chromatic number of a graph and the length of its longest path, or more specifically, the longest path in its complement. To state the theorem formally, let \( G \) be a connected graph.