Edge-Graph Diameter Bounds for Convex Polytopes with Few Facets

We show that the edge graph of a 6-dimensional polytope with 12 facets has diameter at most 6, thus verifying the d-step conjecture of Klee and Walkup in the case d=6. This implies that for all pairs (d, n) with n−d⩽6, the diameter of the edge graph of a d-polytope with n facets is bounded by 6, which proves the Hirsch conjecture for all n−d⩽6. We prove this result by establishing this bound for a more general structure, so-called matroid polytopes, by reduction to a small number of satisfiability problems.