  We analyze the Hilbert space connectivity of the $L$ site PXP-model by
constructing the Hamiltonian matrices via a Gray code numbering of basis
states. The matrices are all formed out of a single Hamiltonian-path backbone
and entries on skew-diagonals. Starting from this observation, we construct an
ensemble of related Hamiltonians based on random graphs with tunable constraint
degree and variable network topology. We study the entanglement structure of
their energy eigenstates and find two classes of weakly-entangled mid-spectrum
states. The first class contains scars that are approximate products of
eigenstates of the subsystems. Their origin can be traced to the
near-orthogonality of random vectors in high-dimensional spaces. The second
class of scars has $\log 2$ entanglement entropy and is tied to the occurrence
of special types of subgraphs. The latter states have some resemblance to the
Lin-Motrunich $\sqrt{2}$-scars.
