🔢 mathematics

A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erd\H{o}s-Gyárfás Conjecture

This paper establishes that any simple cubic bipartite counterexample to the Erdős-Gyárfás conjecture must have at least 60 vertices, a result proven via a certified exhaustive computation that eliminates all such graphs with 58 or fewer vertices.

Original authors: Julius Tranquilli

Published 2026-08-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Julius Tranquilli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world made entirely of connections, where dots (vertices) are linked by lines (edges) to form intricate webs. This is the playground of graph theory, a branch of mathematics that studies how things relate to one another. In this world, a "cubic bipartite graph" is a very specific kind of web: it's a two-sided structure where every single dot is connected to exactly three others, and the dots can be split into two teams such that no two dots on the same team ever touch.

Mathematicians have long been fascinated by a puzzle called the Erdős–Gyárfás conjecture. It asks a simple but stubborn question: If you build a web where every dot has at least three connections, must there always be a loop (a cycle) whose length is a power of two? Think of powers of two as the "magic numbers" of the grid: 4, 8, 16, 32, and so on. The conjecture suggests that no matter how you twist and turn your web, you cannot avoid creating a loop of 4, 8, or 16 links. While this has been proven for some special types of webs, the general case remains a mystery. Solving it would help us understand the fundamental rules of how networks are built, from computer circuits to social groups.

Now, enter a new chapter in this story. A researcher named Julius Tranquilli has taken a massive, computer-assisted step forward in solving this puzzle, specifically for those two-sided, three-connected webs. The paper, titled "A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erdős–Gyárfás Conjecture," doesn't just guess; it performs a certified, exhaustive search to prove that any such web small enough to fit in a certain size limit must contain one of those magic loops.

Here is the big reveal: The paper proves that if you try to build a cubic bipartite graph with 58 vertices or fewer, you simply cannot avoid having a loop of length 4, 8, or 16. It is mathematically impossible to construct a "counterexample" (a web that breaks the rule) that is smaller than 60 vertices. Before this work, the best known limit was 30 vertices. This new result doubles that safety zone, pushing the boundary from 30 all the way up to 60.

How did they do it? The author used a clever trick to translate the problem. They turned the graph problem into a different kind of puzzle involving "incidence configurations," which are like sets of blocks where points are grouped together. They realized that if a graph avoids the forbidden loops, it must contain a specific six-step pattern (a 6-cycle). By treating this pattern as a "root" or a starting seed, they could grow the rest of the graph step-by-step.

They then unleashed a digital army of search algorithms. Imagine a tree growing in a computer, where every branch represents a different way to add a new connection to the graph. The computer grew this tree up to a limit of 29 "points" (which corresponds to 58 vertices in the original graph). It checked every single possible branch to see if it could grow a complete graph without creating a 4, 8, or 16-loop. The result? Every single path hit a dead end. The computer found that no matter how you tried to build it, the rules of the game forced a loop to appear long before you reached the 60-vertex mark.

To make sure the computer didn't make a mistake, the author didn't just run the code once. They built two completely different search programs using different methods to check for the forbidden loops. They also created a "certificate"—a digital receipt that anyone can check to verify the work. Both programs agreed perfectly: zero completions. There were no successful graphs found.

The paper also looked at the "deepest" parts of the search tree, the points where the computer was closest to finding a solution. It found 337 states where the graph was almost complete but still missing a few connections. These states collapsed into just six distinct shapes. When the author analyzed these six shapes, they found that the remaining connections needed to finish the graph would inevitably create a forbidden loop. It was like trying to finish a puzzle only to realize the last piece you need would break the picture.

So, what does this mean? It means that if a counterexample to the Erdős–Gyárfás conjecture exists in the world of cubic bipartite graphs, it must be a giant beast with at least 60 vertices. The "small" monsters have been hunted down and proven to be impossible. While the conjecture itself isn't fully solved (we still don't know if a giant 60+ vertex counterexample exists), this paper has cleared the playing field of all the small possibilities, raising the bar significantly for anyone hoping to find a loophole in the rules of these mathematical webs.

Technical Summary: A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erdős–Gyárfás Conjecture

Problem Statement
The Erdős–Gyárfás conjecture posits that every finite simple graph with a minimum degree of at least three contains a simple cycle whose length is a power of two (i.e., 4, 8, 16, 32, ...). While the conjecture remains open for general graphs, it has been verified for specific restricted classes. This paper focuses on the class of simple cubic bipartite graphs. Prior to this work, the established lower bound for the order (number of vertices) of a potential counterexample in this class was $n \ge 30$ (based on Markström's 2004 computation) or $n \ge 32$ (based on a 2026 public SAT-based computation). The objective was to determine if a counterexample could exist with fewer than 60 vertices.

Methodology
The proof employs a combination of structural graph theory reductions and a certified, exhaustive computer search. The methodology proceeds in three main stages:

Structural Reduction (Moore Bound and Incidence Translation):
- The author first applies an edge-rooted Moore bound argument to show that any simple cubic bipartite graph with at most 58 vertices that avoids cycles of length 4 ( $C_4$ ) and 8 ( $C_8$ ) must necessarily contain a cycle of length 6 ( $C_6$ ).
- The graph is then translated into an incidence structure. A cubic bipartite graph is represented as the Levi graph of a symmetric $v_3$ -configuration (a linear 3-uniform, 3-regular set system with $v$ points and $v$ blocks).
- Under this translation, a $C_6$ in the graph corresponds to a Berge triangle (three blocks intersecting pairwise at distinct points) in the configuration.
- The absence of $C_4$ and $C_8$ in the graph translates to the configuration being linear (no two blocks share more than one point) and containing no Berge cycles of length 4 or 8.
Rooted Search and Normalization:
- By fixing a Berge triangle and applying symmetry reductions, the author demonstrates that up to isomorphism, only two distinct rooted extensions (orbits) are possible for the block passing through a specific point in the triangle.
- This reduces the problem to a restricted-growth search on these two specific root orbits. The search generates configurations by adding points and blocks in lexicographic order, maintaining a "point cap" of 29 (since $2v \le 58 \implies v \le 29$ ).
- The search terminates a branch if it creates a forbidden Berge cycle (length 4 or 8) or if it reaches a state where no further blocks can be added without violating constraints.
Certified Exhaustive Computation:
- Two independent implementations of the search were executed using different algorithms for the $C_{16}$ oracle (detecting cycles of length 16):
  - Implementation A: Uses simple-path Depth-First Search (DFS).
  - Implementation B: Joins complete lists of 7-edge half-paths.
- Both searches utilized a static witness certificate system. A streaming checker reconstructs the search tree, validates positive cycle witnesses, and verifies that no completed configuration (where all points have degree 3) exists within the cap of 29 points.
- The search was verified against known census data for smaller configurations ( $v \le 13$ ) to ensure the generator's correctness.

Key Results

Theorem 1: Every simple cubic bipartite graph with $|V(G)| \le 58$ contains a simple cycle of length 4, 8, or 16.
Corollary 2: Any simple cubic bipartite counterexample to the Erdős–Gyárfás conjecture must have at least 60 vertices.
Search Statistics: The exhaustive search covered two root orbits with a total of 21,493 states and 1,762,368 attempted extensions. Crucially, zero completions were found in either orbit.
Terminal Obstruction: The search identified 337 surviving states at the maximum depth (19 blocks, utilizing all 29 points). These states collapsed into six isomorphism classes (kernels). Analysis of the "compatible-pair graphs" for these kernels revealed they are forests (triangle-free), proving that no 20th block can be added to any of these states without creating a $C_4$ , $C_8$ , or $C_{16}$ .

Significance and Claims
The paper claims to raise the established lower bound for cubic bipartite counterexamples from $n \ge 30$ (or $n \ge 32$ ) to $n \ge 60$ .

Strength of Result: The result is stated in a stronger form than a mere verification of the conjecture; it proves that one of the first three relevant power-of-two cycle lengths (4, 8, or 16) is forced in this class for graphs up to 58 vertices. It explicitly notes that a 32-cycle is not required to establish this bound.
Verification: The result is supported by a "certified exhaustive computation" involving two separate implementations with different oracles and a static certificate checker, ensuring the result is not an artifact of a single software bug.
Limitations: The paper explicitly states that the computation does not examine side size 30 (60 vertices) and therefore does not rule out the existence of a counterexample at exactly 60 vertices. The work establishes the frontier inside the class up to 58 vertices.

Artifacts
The author provides full reproducibility, including source code, certificates, logs, and verification programs, archived on Zenodo (DOI: 10.5281/zenodo.21695513) and a GitHub repository. The paper also discloses that OpenAI tools (ChatGPT and Codex) assisted in code development, structural approach formulation, and manuscript drafting, but the mathematical arguments and evidentiary basis rest on the retained code, logs, and certificates.

Technical Summary: A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erdős–Gyárfás Conjecture

More like this