gpt 6 astra ultra attempt on Math-1130

The Bollobás-Eldridge-Catlin Conjecture on graph packing

Definitions and mathematical statement

Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be finite simple graphs with $|V_1|=|V_2|=n\ge1$. Their maximum degrees are $\Delta_i=\max_{v\in V_i}d_{G_i}(v)$. The graphs pack if there is a bijection $\varphi:V_1\to V_2$ such that \[ uv\in E_1\quad\Longrightarrow\quad \varphi(u)\varphi(v)\notin E_2. \] Thus, after relabelling one graph, the two edge sets are disjoint on a common set of $n$ vertices. Equivalently, $G_1$ is isomorphic to a spanning subgraph of the complement of $G_2$. Nonedges of $G_1$ impose no constraint, so the embedding need not be induced.

The catalogue's Bollobás--Eldridge--Catlin conjecture asserts that \[ (\Delta_1+1)(\Delta_2+1)<n+1 \quad\Longrightarrow\quad G_1,G_2\text{ pack}. \] The strict inequality is retained exactly. Since both sides are integers, its hypothesis is equivalent to $(\Delta_1+1)(\Delta_2+1)\le n$, not to the stronger boundary version with $\le n+1$.

The bijection is chosen freely; no initial matching of vertex labels must be respected. Isolated vertices count towards $n$ and must also be placed. The target concerns every pair of graphs meeting this maximum-degree condition, independently of their component structures or numbers of edges. Packing uses the same host vertices for both graphs and therefore does not mean making their vertex sets disjoint.

Short English statement

Can two n-vertex graphs be relabelled to have no common edge whenever the product of one plus their maximum degrees is less than n+1?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 2 October 2026. The canonical formulation above is retained. This attempt uses a primary-source literature audit, independent restricted proofs, and adversarial checks. Reproved results are not claimed as new. Numerical tests below are reproducible in scripts/check_attempt_batch03_extremal_2026_10_02.py.

Literature and chosen attack.

The original question [S2] concerns arbitrary simple graphs. The 2026 paper [S3] breaks the proposed degree barrier for specified bipartite settings with additional hypotheses; that is not a proof of the unrestricted statement. The switching argument below independently recovers the classical Sauer--Spencer sufficient condition, discussed in [S4], and checks exactly which catalogue cases it covers.

A complete switching lemma.

Write $a=\Delta(G_1)$ and $b=\Delta(G_2)$. We prove that $n>2ab$ suffices for packing. If either maximum degree is zero, every bijection works. Otherwise place red and blue copies of the two graphs on the same $n$ labelled vertices, choosing the red placement to minimize the number of edges present in both colours. Suppose that $uv$ is such a common edge. Set \[ B=\bigcup_{x\in N_R(u)}N_B(x),\qquad C=\bigcup_{y\in N_B(u)}N_R(y). \] Both sets have size at most $ab$. Moreover $u$ belongs to both: the common neighbour $v$ witnesses this. Consequently \[ |B\cup C\cup\{v\}|\le 2ab. \] There is a vertex $w$ outside this union. In particular $w\ne u,v$. Swap the red labels $u,w$, leaving the blue graph fixed.

An edge whose endpoints avoid $u,w$ is unaffected, as is the unordered pair $uw$. A new red edge $wx$ with $x\ne u,w$ originated at $ux$; if $wx$ were blue, then $w\in N_B(x)\subseteq B$, impossible. A new red edge $ux$ originated at $wx$; if $ux$ were blue, then $w\in N_R(x)\subseteq C$, also impossible. Thus the switch creates no common edge. The old common edge $uv$ disappears as a conflict, since all resulting red edges incident with $u$, apart from $uw$, have just been checked. This strictly decreases the overlap, a contradiction. A placement with no overlap therefore exists.

Where this proves the catalogue inequality.

Since $n,a,b$ are integers, the displayed hypothesis in the definition says $(a+1)(b+1)\le n$. If $a=1$, it gives $n\ge2b+2>2ab$; symmetry handles $b=1$. If $a=b=2$, it gives $n\ge9>8=2ab$. These cases, together with zero degree, are completely covered. More generally every instance satisfying both the catalogue condition and $n>2ab$ is covered. For large $a,b$, however, $(a+1)(b+1)$ is close to $ab$, not $2ab$. The two forbidden sets can jointly use almost twice the budget permitted by the conjecture.

A sharpness test for the weaker lemma.

Let $d\ge3$ be odd, $n=2d$, let the red graph be a perfect matching, and let the blue graph be $K_{d,d}$. Packing would place the red matching in the complement, which is the disjoint union of two copies of $K_d$. Each component has odd order, so it has no perfect matching; edges between the two components are unavailable. Packing is impossible. Here $2ab=2d=n$, showing that simply replacing the strict inequality in our lemma by a weak one is false. This is not a counterexample to the catalogue conjecture: $(a+1)(b+1)=2d+2>n$.

Verification and first gap.

The script enumerates all placements for the $d=3$ obstruction and finds no packing. The proof checks the potentially troublesome unchanged edge $uw$ separately and uses the common edge to save one vertex in the union bound. No planarity, bipartiteness, or regularity is used in the lemma. Improving the argument requires correlated control of $B$ and $C$, or a switch involving more vertices, strong enough to bridge $2ab$ to $(a+1)(b+1)$ for arbitrary degree pairs. Such control has not been proved here.

Final status.

The stated degree region and low-degree cases are proved; the full Bollobás--Eldridge--Catlin target remains UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3287 (OPG-48232), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, The Bollobás-Eldridge-Catlin Conjecture on graph packing. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/the_bollobas_eldridge_catlin_conjecture_on_graph_packing.
• S3 P. Allen, J. Böttcher, J. Skokan and B. Sudakov, Breaking the Bollobás--Eldridge--Catlin barrier for bipartite graphs $2026$, arXiv:2607.17808. Additional bipartite hypotheses matter. https://arxiv.org/abs/2607.17808.
• S4 P. Allen, J. Böttcher, Y. Kohayakawa and R. Neve, Robustness of the Sauer--Spencer Theorem $2025$, arXiv:2507.03676. https://arxiv.org/abs/2507.03676.