On path lengths modulo three
Xiaotie Deng, Christos H. Papadimitriou · Journal of Graph Theory · 1991
Abstract We show that between any two nodes of a cubic, planar, three‐connected graph there are three paths whose lengths are 0, 1, and 2 modulo 3, respectively. The proof is by a rather extensive case analysis. Counterexamples show that all three hypotheses (i.e., planarity, degree‐three, and three‐connectivity) are necessary.