Edge-following methods, such as the simplex method, move along edges of a polytope. Their behavior depends on which vertices are adjacent and on the diameter. We study both for the two polytopes of binary polynomial optimization: the multilinear polytope and its standard linear relaxation. For quadratic polynomials, Padberg showed that two integral vertices are adjacent in both polytopes if and only if the variables where they differ induce a connected subgraph. For higher degree, we replace this subgraph by a contracted hypergraph on the same variables, built from the monomials whose constraints tie these variables together. We show that its connectivity decides adjacency in the relaxation but, unlike in the quadratic case, not always in the multilinear polytope. Adjacency is the same in both polytopes exactly when the relaxation has the Trubin property. We investigate when this property holds and characterize it for cubic polynomials. The contracted hypergraph also yields short paths. The diameter of the multilinear polytope is at most the number of variables, and that of the relaxation is linear in the numbers of variables and monomials. Similar linear bounds hold for the number of pivots between bases of the relaxation.