---
tag: CSS694B7NR
kind: statement
role: proposition
name: Gallai–Hasse–Roy–Vitaver theorem
sources:
  - wikipedia: en:36620043@r1345571774
    locator: Gallai–Hasse–Roy–Vitaver theorem
    note: adopted
    mention: wikipedia://en/36620043
    sections: [Statement]
same_as:
  wikidata: Q5518852
  wikipedia: Gallai–Hasse–Roy–Vitaver theorem
inventory: [D5F9TS715K]
---

## Statement

In graph theory, the **Gallai–Hasse–Roy–Vitaver theorem** is a form of [[duality|QS4283K3FK]] between the [[colorings|0NCPXH194Y]] of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph $G$ equals one plus the length of a longest path in an orientation of $G$ chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.