The conjecture says every graph with minimum degree 3 contains a cycle whose length is a power of two. Reformulated as a single inequality between two integer sequences, it becomes checkable — and the current data reduces the next open case to three numbers.
Erdős and Gyárfás asked in 1995 whether every finite graph with minimum degree at least three must contain a cycle whose length is a power of two — a cycle of length 4, 8, 16, 32, and so on. Erdős reportedly expected the answer to be no, and offered a reward either way.
It is still open. The computational lower bound on a counterexample is 17 vertices (30 if cubic), from a 2004 search by Royle and Markström. Partial results cover 3-connected cubic planar graphs, claw-free graphs, P₁₃-free graphs, and diameter-2 graphs.
What follows is a reformulation, a barrier result explaining why the standard machinery cannot close it, and a finite reduction of the next open case. Every numeric claim is tagged with how it was established.
The key observation is that a graph on n vertices cannot contain a cycle longer than n. So a counterexample only has to dodge the powers of two that are at most n — every larger one is absent for free. That turns "avoid all powers of two" into a finite condition indexed by the size of the graph.
Geoffrey Exoo defines a sequence that measures exactly this cost. Let
f(k) = the smallest order of a cubic graph having no cycle of length 2m for any m ≤ k.
Known values: f(2) = 10 (the Petersen graph and two others), f(3) = 24 (Markström, four minimal graphs), f(4) ∈ [54, 78], and f(5) ≤ 450. Exoo introduced these to bound how large the smallest power-of-two cycle can be forced to get. But they answer the conjecture itself:
The Erdős–Gyárfás conjecture is false for cubic graphs if and only if f(k) ≤ 2k+1 − 1 for some k ≥ 2.
Suppose f(k) = N ≤ 2k+1 − 1 and let G be a witness. Then G has N vertices and no 2m-cycle for m ≤ k. Since N < 2k+1, the powers of two not exceeding N are exactly 4, 8, …, 2k — all of them absent. So G is a counterexample. Conversely, given a cubic counterexample on n vertices, put k = ⌊log₂ n⌋; it avoids every 2m with m ≤ k, so f(k) ≤ n ≤ 2k+1 − 1.
The same argument runs verbatim with f*(k), the minimum over all graphs of minimum degree ≥ 3 rather than just cubic ones, giving the conjecture in full. The cubic version is the one with data behind it, and Carr's 2026 result — every minimal counterexample has at least 4/7 of its vertices of degree exactly 3 — is the reason to expect the cubic case carries the weight. Measured f* values appear below; they exist nowhere in the literature.
So the conjecture is precisely the statement that one integer sequence outruns another. Here is the race as it currently stands.
| k | f(k) lower | f(k) upper | 2ᵏ⁺¹ | margin | log₂f − k | status of the value |
|---|---|---|---|---|---|---|
| 2 | 10 | 10 | 8 | +2 | 1.322 | Exact. Reproduced here: exactly 3 cubic graphs of order 10 with no 4-cycle, none smaller. |
| 3 | 24 | 24 | 16 | +8 | 1.585 | Exact (Markström 2004, four minimal graphs). Reproduced here up to order 20. |
| 4 | 54 | 78 | 32 | +22 | ≥1.755 | Lower bound now sourced: Markström's data page records a complete search of all cubic graphs on N ≤ 52 for {4,8,16}-avoidance, with none found. Upper bound is Exoo's G₇₈. |
| 5 | ? | 450 ⚠ | 64 | ? | ? | No published lower bound exists — the first genuinely unguarded rung. The upper bound is also in doubt: see §6. |
Two things stand out. The normalised gap α(k) = log₂ f(k) − k is increasing — 1.32, 1.59, ≥1.76 — so the sequence is not merely ahead, it is pulling away. And the observed growth ratios, 24/10 = 2.4 and ≥54/24 = 2.25, both exceed 2. That suggests a clean sufficient condition.
If f(k+1) ≥ 2·f(k) for all k ≥ 2, the Erdős–Gyárfás conjecture holds for cubic graphs.
By induction from f(2) = 10, doubling gives f(k) ≥ 10·2k−2 = 2.5·2k > 2k+1 − 1. Apply Proposition 1.
This converts a statement quantified over all graphs into a monotonicity property of one integer sequence: avoiding one more power of two must at least double the order required. That is a far more tractable-looking target, and it is what the two known ratios already satisfy. The honest caveat is that neither Proposition 1 nor 2 is a proof of anything — they relocate the difficulty into a lower bound on f, and no general lower bound on f(k) has ever been published. That absence is the real state of the problem.
There is a large and successful literature on forcing a graph to have many distinct cycle lengths. Bondy–Vince (1998) get two cycles differing by one or two from minimum degree three; Fan, Liu–Ma, and Gao–Huo–Liu–Ma extend this to k cycles in arithmetic progression from minimum degree k+1; and Bucić–Gishboliner–Sudakov recently proved that a Hamiltonian graph with minimum degree three has n1−o(1) distinct cycle lengths, nearly settling conjectures of Jacobson–Lehel and Verstraëte.
None of it can settle this conjecture, for a reason that is embarrassingly simple once stated.
No lower bound on the number of distinct cycle lengths can prove Erdős–Gyárfás — not even the strongest conceivable one short of "all but o(log n) lengths," which is false.
A counterexample on n vertices must dodge the set of powers of two in [3, n], of size ⌊log₂ n⌋ − 1. Its spectrum lives in [3, n], of size n − 2. A graph realising n − ⌊log₂ n⌋ − 1 distinct lengths — that is, all but a o(1) fraction — can still miss precisely the powers of two. Cardinality alone never separates the two cases.
| n | available lengths in [3,n] | powers of two to dodge | fraction that must be missed |
|---|---|---|---|
| 16 | 14 | 3 | 21.4% |
| 32 | 30 | 4 | 13.3% |
| 100 | 98 | 5 | 5.1% |
| 1 000 | 998 | 8 | 0.80% |
| 1 000 000 | 999 998 | 18 | 0.0018% |
The target set is exponentially sparse. Even a theorem asserting that every minimum-degree-3 graph has n − 20 distinct cycle lengths would leave the conjecture untouched for large n. Erdős–Gyárfás is not a density statement; it requires a mechanism that produces a cycle of a prescribed length. That is why the consecutive-lengths line stalls here: at minimum degree exactly 3 it yields two near-consecutive lengths, and the conjecture needs roughly log₂ n of them, at exponentially spaced positions.
The most natural way to build a counterexample is to make all cycle lengths share a residue that no power of two can have. Since 2k mod 3 ∈ {1, 2}, a graph in which every cycle length is divisible by 3 would dodge every power of two at once. Likewise ≡ 0 mod 5, or ≡ 3 mod 7. All of these are dead on arrival.
For any m ≥ 3, no graph with minimum degree at least 3 has all of its cycle lengths in a single residue class mod m. In particular, every such graph has a cycle of length not divisible by 3.
Bondy–Vince: every simple graph with at most two vertices of degree less than three, other than K₁ and K₂, has two cycles whose lengths differ by one or two. Two lengths in the same class mod m differ by a multiple of m ≥ 3.
This is a one-line consequence of a 1998 theorem, and I could not find it stated anywhere. It pairs neatly with Chen–Saito, which gives the complementary half: every graph with minimum degree ≥ 2 and at most one vertex of degree 2 does contain a cycle of length divisible by 3. Together: such a graph always has both kinds of cycle.
A second natural construction dies just as fast. If every cycle were odd, no power of two could appear. But a theta subgraph with internally disjoint paths of lengths a, b, c yields cycles of lengths a+b, a+c, b+c, summing to 2(a+b+c) — even, so they cannot all be odd. Hence every block of an even-cycle-free graph is an edge or an odd cycle, and minimum degree drops to 2.
The gaps between consecutive powers of two are wide — the interval (2k, 2k+1) has 2k − 1 integers in it. A counterexample whose entire cycle spectrum fits inside one such gap would be automatic. That route closes too, and for a satisfying reason: fitting inside the gap forces girth > 2k, and high girth forces many vertices, and many vertices force a long cycle — back out of the gap.
| k | gap | girth ≥ | forces n ≥ | forces circumference ≥ | gap ceiling | verdict |
|---|---|---|---|---|---|---|
| 2 | 5 – 7 | 5 | 10 | 5.8 | 7 | Bound too weak — settled by direct search instead (see below). |
| 3 | 9 – 15 | 9 | 58 | 23.7 | 15 | Closed. |
| 4 | 17 – 31 | 17 | 768 | 187.4 | 31 | Closed. |
| 5 | 33 – 63 | 33 | 196 606 | 15 828 | 63 | Closed by a factor of 250. |
| 6 | 65 – 127 | 65 | 1.3 × 10¹⁰ | 1.1 × 10⁸ | 127 | Closed by a factor of 10⁶. |
Vertex counts are Moore bounds sharpened by known cage orders; circumference uses Liu–Yu–Zhang's Ω(n0.8) bound for 3-connected cubic graphs, with their explicit constant 0.922. The mismatch is not close — the Moore bound is doubly exponential in k while the gap ceiling is only singly exponential, so the margin explodes.
The hypothesis is load-bearing and I want to be exact about it. The circumference bound needs 3-connectivity, not just minimum degree 3. Without it the argument collapses: chain t copies of K₄ together with single bridges and you get a connected graph of minimum degree 3, arbitrarily many vertices, and circumference exactly 4. So Proposition 5 below is stated for 3-connected cubic graphs, and extending it is open.
For k ≥ 3, no 3-connected cubic counterexample has its cycle spectrum contained in (2k, 2k+1). A counterexample must straddle a power of two — containing cycles both shorter and longer than some 2k while containing none of that exact length.
The remaining case k = 2 is where the asymptotic bound is too weak to bite, so I checked it directly: over all connected graphs with minimum degree ≥ 3 and girth ≥ 5 on up to 17 vertices — 26 731 graphs in total — none has circumference ≤ 7. The gap 5–7 is empty in the range where it could plausibly be occupied.
Straddling is a much more delicate property than dodging. It means the spectrum has a hole at exactly one exponentially-placed value, with material on both sides — precisely the configuration that no known theorem produces or forbids.
Proposition 1 does more than restate the problem — it bounds the search. A cubic counterexample with ⌊log₂ n⌋ = 4 lives on n ∈ [16, 31] and must avoid cycles of length 4, 8, and 16, and nothing else. Since f(3) = 24, it has at least 24 vertices; cubic graphs have even order; and Markström's four minimal order-24 graphs all contain 16-cycles.
The entire cubic case of Erdős–Gyárfás for n ≤ 31 reduces to three orders: n = 26, 28, 30. For each, the question is whether any connected cubic graph with no 4-cycle also avoids both 8-cycles and 16-cycles.
All three orders were settled by Markström; the k = 4 case is closed. His paper covers every cubic order below 29, and his data page goes considerably further: a complete search of all cubic graphs on N ≤ 52 avoiding cycles of length 4, 8 and 16, finding none. That is simultaneously the source of the widely-quoted "any cubic counterexample needs at least 30 vertices" and of the f(4) ≥ 54 bound Exoo could only cite as unpublished.
That particular reduction is now moot, since f(4) ≥ 54 is established outright. But the same argument applied one rung up is not moot, and it locates the actual frontier:
A cubic counterexample with ⌊log₂ n⌋ = 5 needs 54 ≤ n ≤ 63 and must avoid cycles of length 4, 8, 16 and 32 — nothing more. Markström's sweep rules out everything up to n = 52 even for the weaker condition. So the first genuinely untested case is five orders wide:
n ∈ {54, 56, 58, 60, 62}
Settling f(5) in full is not required and would be far more work — a counterexample cannot hide above 63, because at n ≥ 64 the graph must also dodge 64 and the question moves to k = 6.
Brute-force enumeration is hopeless at that size; Markström reached 52 with a modified minibaum that prunes on cycle length during generation rather than filtering afterwards, and extending that by five orders is the concrete next step.
Checking the top rung of the table turned up a problem with it. Exoo's G₄₅₀ is built by replacing every vertex of the Tutte–Coxeter graph with a 15-vertex gadget H₁₅. The paper justifies the absence of 32-cycles in one sentence:
"This follows from the observation that any 8-cycle in Tutte–Coxeter contains (at least) two consecutive edges on the outer Hamiltonian cycle, and therefore at least one v-w path in a copy of H₁₅."
— arXiv:1403.5636, §4
That observation is false, and the check is small enough to be decisive. The Tutte–Coxeter graph has girth 8 and exactly 90 distinct 8-cycles. Enumerating all of them and testing each against the stated property:
10 of the 90 8-cycles — 11% — use no two consecutive outer-Hamiltonian-cycle edges. Each of the ten alternates strictly between outer edges and chords, using four of each in positions 0,2,4,6 around the cycle. Example: 0–1–22–23–6–5–18–17.
So the argument for f(5) ≤ 450 has a genuine gap. Whether the conclusion also fails is a separate question and I am less certain of it: a reconstruction of G₄₅₀ from the paper's own TikZ source — with the gadget distances and all fifteen Tutte–Coxeter chords matching the paper vertex-for-vertex — does contain a 32-cycle, and it projects onto exactly one of the ten offending 8-cycles. That is strong circumstantial agreement, but it still rests on a reconstruction rather than the author's original code, so I state it as likely, not established.
The construction data is not recoverable from the public record. Exoo's graph pages carry drawings only — GIF images, no adjacency lists — and an Internet Archive listing of his former host shows the same six pages and nothing else: no G₇₈, no G₄₅₀, no G₅₄₀, no graph6 files. His site does still state, in a page last modified in 2010 and so predating the paper, that the smallest graph he knew of with no 4-, 8-, 16- or 32-cycle had 540 vertices. That is the earlier bound the paper's 450 was meant to improve on, not a retraction of it — but it is the figure f(5) would fall back to if G₄₅₀ does not survive scrutiny.
This does not disturb anything above. The propositions use lower bounds on f; an upper bound falling away means f(5) may be larger than 450, which puts the sequence even further ahead of 2ᵏ⁺¹. The effect on the race is to remove a data point, not to move one in the dangerous direction. Exoo's other two graphs came through clean: G₇₈ and G₄₂₀ were both independently confirmed to have no 4-, 8-, or 16-cycle, and both were found to contain 32-cycles — so for each the smallest power-of-two cycle is exactly 2⁵, a fact the paper does not state.
Carr (2026) proves three facts about a minimal counterexample G — one of smallest order, and subject to that, smallest size. His Lemma 0.1 is the engine: no proper subgraph of G has minimum degree ≥ 3, since such a subgraph would be a smaller counterexample. From it he derives:
His Theorem 0.1 then concludes that at least 4/7 of the vertices are cubic. But that proof uses only (2). Statement (1) is proved and never applied, and it is worth a good deal:
At least 2/3 of the vertices of a minimal counterexample have degree exactly 3.
Write V₃ and V₄₊ for the vertices of degree exactly 3 and at least 4. Let v ∈ V₃. By (1), v has a neighbour of degree exactly 3, i.e. a neighbour inside V₃ — so at most 2 of its 3 edges leave V₃, giving e(V₃, V₄₊) ≤ 2|V₃|. By (2), V₄₊ is independent, so every edge at a vertex of V₄₊ lands in V₃, and each such vertex has degree ≥ 4, giving e(V₃, V₄₊) ≥ 4|V₄₊|. Hence 4|V₄₊| ≤ 2|V₃|, so |V₄₊| ≤ |V₃|/2 and n = |V₃| + |V₄₊| ≤ (3/2)|V₃|.
Carr's step bounds e(V₃, V₄₊) by 3|V₃|, allowing a cubic vertex to send all three edges to high-degree vertices. His own Corollary 0.1(1) forbids exactly that. The constant improves from 0.571 to 0.667.
And 2/3 is the ceiling for this argument. Equality needs every vertex of V₄₊ to have degree exactly 4 and every vertex of V₃ to have exactly one neighbour in V₃ — a configuration that exists: take 8 cubic vertices in a perfect matching, 4 vertices of degree 4, and join each cubic vertex to two of the latter so each receives four edges. That graph is simple, has V₄₊ independent, has every vertex adjacent to a cubic vertex, and hits 8/12 = 2/3 exactly. So no further gain is available without a new structural input.
A second observation for that paper. Lemma 0.1 says precisely that a minimal counterexample has no proper subgraph of minimum degree 3 — that is, it is degree-3-critical, a class with its own literature that the note does not cite. Bollobás and Brightwell (1989) proved every such graph has a cycle of length ≥ 4log₂n − o(log n) and built examples where the circumference is only 4log₂n + O(1); Narins, Pokrovskiy and Szabó conjecture that every degree-3-critical graph has at least 3log₂n + O(1) distinct cycle lengths. Those are statements about exactly the object Lemma 0.1 defines. Note also that the connection is only informative in the non-cubic case: every cubic graph is trivially degree-3-critical.
All searches used nauty-geng for generation and an exact cycle-length test — for target length L, a depth-capped DFS from each start vertex over paths visiting only larger vertices, so each cycle is found once from its minimum vertex.
nauty-labelg, his 23 graphs and mine agree graph-for-graph, with zero differences in either direction; the same holds for all four graphs at order 24. It is verification, not extension — I built it believing the count was unknown, which was wrong.Exoo's f is defined over cubic graphs. Writing f*(k) for the same quantity over all graphs of minimum degree ≥ 3, no values appear anywhere in the literature. Two rungs:
| n | connected, δ≥3, C₄-free | also C₈-free | note |
|---|---|---|---|
| 5–9 | 0 | 0 | Minimum degree 3 and no 4-cycle already forces 10 vertices. |
| 10 | 5 | 0 | 3 cubic (= f(2)) plus 2 non-cubic, both of degree sequence [3⁸,4²]. |
| 11 | 9 | 0 | |
| 12 | 57 | 0 | |
| 13 | 503 | 0 | |
| 14 | 6 059 | 0 | |
| 15 | 91 433 | 0 | |
| 16–23 | — | — | Not searched. So 16 ≤ f*(3) ≤ 24, the upper bound by inheritance from the cubic case. |
So f*(2) = 10, exactly as in the cubic case — dropping regularity buys nothing at the first rung. The two extra extremal graphs are worth noting: in one of them the two degree-4 vertices are non-adjacent, which is exactly the configuration Markström's structural observation says a minimal counterexample must contain (an independent set of degree-≥4 vertices alongside degree-3 vertices). Both nevertheless contain 8-cycles, with full spectrum {3,5,6,7,8,9,10}.
Recovered independently; graph6 format, cubic, girth 3, no 4- or 8-cycle, all containing a 16-cycle. The fourth is the planar one.
| # | graph6 | planar |
|---|---|---|
| 1 | W??G?C??KCCBa?OCgO@O@C??O?IG??G?K`??CO?K@???C@@ | no |
| 2 | WK?Y?CAGK?G`?G??_?O_@????@WOO@O?C@O??OOK??O??D@ | no |
| 3 | W?GG?C??CO?FW?P?q??g@?_@A?GA??a?E?_??GAH?_??A?P | no |
| 4 | W?O@??O@COO@O_O?c?@?`c??P?GGG?W?C@@??o?G@@??E?@ | yes |
A partial pass over order 26 turned up a cubic graph missing two of the three relevant powers of two. Its cycle spectrum is {3, 5, 6, 7, 9, 10, 11, …, 26} — every length from 3 to 26 except 4 and 8. It contains a 16-cycle, so it is not a counterexample.
So the object is not arbitrary. It is a 24-vertex graph with one vertex blown up into a triangle, and that single operation does all the work. Expanding a vertex lengthens every cycle through it by one and leaves every other cycle alone. The question is whether you can find a vertex that all the unwanted cycles happen to pass through.
The 24-vertex contraction has exactly nine 8-cycles, and all nine run through the expanded vertex. Blowing it up moves every one of them to length 9 and leaves nothing at 8. The ten 7-cycles all avoid that vertex, so they stay at 7 and never arrive at 8 from below.
That is Markström's and Exoo's gadget method in its smallest possible form — not a 7-vertex gadget applied wholesale, but a single triangle placed at the one vertex where it annihilates an entire cycle length. It also sharpens §2: this graph realises 22 of its 24 available cycle lengths. Dodging powers of two has nothing to do with having a sparse spectrum, and everything to do with a local operation that shifts one length off a target.
Where order 24 has four graphs avoiding 4- and 8-cycles, order 26 has 23 — a count Markström reports in his Table 3, alongside 251 at order 28. He draws the four order-24 graphs but does not list the order-26 family, so the graph6 strings and the structural breakdown below are the part of this that is not already in print. All 23 are cubic and connected; none is planar; all contain 16-cycles.
The striking regularity is triangles. Every one of the 23 has at least one, with counts running over every value from 1 to 8 — and the same was true of all four graphs at order 24. Not a single extremal graph at either order has girth 5. That is why the girth ≥ 5 shortcut, which shrinks the search by a factor of 60, would have returned a clean sweep of nothing and looked like a result.
| # | graph6 — cubic, order 26, no C₄, no C₈, contains C₁₆ |
|---|---|
| 1 | Y??H?A??E?O@O?OOe?@?@C??OOGOG?O?cD??@C?GCC??W?@?GA??K??_ |
| 2 | Y??H?A??E?O@O?OOe?@?@CG?O?GOG?O?cD??@C?GCC??W?@?C@??K??_ |
| 3 | Y??K??Q?X???OA?@w?C?@K??_?GO?_O?KC@?@C?Ga???W?@O@???B??_ |
| 4 | Y??K??Q?X???o?_?g?A?HK??_?GOA?O?KCC?@C?Ga???W?@?AG??B??_ |
| 5 | Y?GG?A???O?F??D?q??E@W?@C?GD?AC?C@??CO?H?_??A?D_?_??A_?_ |
| 6 | Y?GG?A???O?F_A??q??E@W?@C?GD?AC?C@??CO?H?_??A?DC?O?@?O?_ |
| 7 | Y?GG?A?G?O?@_A??q??E@W?@C?GD?AC?C@O?CO?G@G??A_@C?O?@?O?_ |
| 8 | Y?GI????CO?F??C??W??FW?@C?K_??g?C@A??OOK@???S?@GC???C_?_ |
| 9 | Y?GI???G?O?F_A??q??C@G??@?Y??QG?C@O?CO?K@???S?@C?O?@?O?_ |
| 10 | Y?GI?C??CO?F??C?K?AG@c??S?GA??AAE?_??g?H?_??AO@??__??o?_ |
| 11 | Y?GI?C??CO?F??C?K?AG@c??S?K@??D?C_O??C_GAC???O@?OO???O@_ |
| 12 | Y?HA@C?WGO?@??B?o??G?_G?A_G_G?AGE?A??A_G_@???C@C?C???C@_ |
| 13 | Y?HI@c??G?G@A???o?C?DC??S?K@??@?S?S??C?G?P??P?@G?O???OC_ |
| 14 | Y?`W@c??C_G@????D???F?`??oG@??D?D?O??C?K?C???OPG?O???OC_ |
| 15 | Y?hO@AO?GCCB_AOC`??C@@??@?QC????S??`??@Ga?????@??A@???D_ |
| 16 | YC?I?OOA??A?___?k?A?PG??_OGGO?G?C@@??o?G@?O?E?@?@?O?B??_ |
| 17 | YCGA@EAGG?AH?AA?_?O_@AA???K?@???D?O?P??GG?G??G`@??O??CO_ |
| 18 | YCHY@CA?G??B??CO????F????aH?G??@E?A?_?GG?OA@@?@O?A??CA?_ |
| 19 | YG@G?c?GW@??_?@?A?O_@A@?g?GD?AC?E?G??A?K?G???_B??S???o?_ |
| 20 | YK?I??O?A?A?_?_Oc?@?`AO?GOGCC?E?C?__?K?GGO??@?@@@???@?@_ |
| 21 | YK?Y?CAGCO?E???@_C??RO??G?H??G??C@O?CO?K?C???S@@??O??AO_ |
| 22 | YKHA?_AGOO?F????_C??S??GB?G?C?g?C??A??KK??OO??DA?O?@?O?_ |
| 23 | Y_?K??Q@X??__???G@A?@K??_@GO??OACP???o?G?G_?@_@??__??o?_ |
nauty-geng is the obvious generator and the wrong one. Asked for cubic graphs it enumerates everything and filters down to 3-regular, running at roughly 145 graphs per second per core — generation-bound, with the cycle test idling at under 1% CPU. At that rate order 26 is a multi-day job.
snarkhunter (Brinkmann–Goedgebeur) constructs cubic graphs directly and runs the same pipeline at about 385 000 graphs per second — a factor of 2 600. Order 24 goes from "never finished" to 295 seconds, which is the difference between guessing at Markström's four graphs and simply producing them. It is not packaged anywhere; building it also requires compiling nauty from source for its static libraries. Everything above is snarkhunter n 3 s o g piped into about eighty lines of C.
Girth is the trap. snarkhunter takes a minimum girth, and it is tempting to ask for girth ≥ 5 since that makes the search tiny. That would be wrong: 3 is not a power of two, so triangles are perfectly legal in a counterexample — and in fact all four of the order-24 extremal graphs have girth 3. The girth ≥ 5 runs above are a genuine but partial slice, about 1.5% of the space at order 26.