Hoffman-Kruskal Theorem states that then A is totally unimodular if and only if, for every integral vector b for which the polyhedron is non-empty, \ x R n : Ax b,\ x 0\ is integral. It is a structural result used to certify optimality and guide algorithms in combinatorial optimisation.