A cheap, verifiable way to bound the diameter of a large vertex-transitive graph within a factor of two. The key fact is that in any vertex-transitive graph the diameter D is at most twice the average distance mu between vertices (D < 2mu), a consequence of the graph looking the same from every vertex. Rather than searching for the exact diameter, one estimates mu statistically: draw states uniformly at random, use a fast solver to obtain an upper bound on each sample's distance to a fixed target, and apply a concentration inequality (e.g. Hoeffding) to certify the true average with a stated confidence and error bar. The certified average then yields a high-confidence diameter bound of at most 2mu. The canonical instantiation is the 3x3x3 Rubik's Cube, whose Cayley graph has an average solving distance near 18.32 moves, giving a reproducible 36-move diameter bound - a 'demigod number' that trades tightness (versus the exact 20-move 'God's Number') for being easy to understand, reproduce, and verify. The technique is general: it applies to any vertex-transitive graph where distances can be upper-bounded per sample.
For any vertex-transitive graph - one whose automorphism group acts transitively on vertices, so every vertex 'looks the same' - the diameter D (the largest shortest-path distance between two vertice…