Math 2.0

Proposition

Gallai–Hasse–Roy–Vitaver theorem

Statement

In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings 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 GG equals one plus the length of a longest path in an orientation of GG chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first. The path takes the proof Proof of Gallai–Hasse–Roy–Vitaver theorem.

Show the path as a graph
Proof of Gallai–Hasse–Roy–Vitaver theorem, proof, no evidence levelProof of Gallai–Hasse…proofGallai–Hasse–Roy–Vitaver theorem, statement, no evidence levelGallai–Hasse–Roy–Vita…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Proof of Gallai–Hasse–Roy–Vitaver theorem proof
  2. Gallai–Hasse–Roy–Vitaver theorem statement

Further reading

  1. Wikipedia, page 36620043, revision 1345571774, Gallai–Hasse–Roy–Vitaver theorem. adopted
About this page
TagCSS694B7NR
URIm2://CSS694B7NR
Kindstatement, proposition
WritingW0 stub
StatusThis copy of the site has no build data. Run m2 status CSS694B7NR.
Same as
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • edge uses out: each definition that the statement needs (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Proofs