ProbXiv
sign in

Largest Bipartite Subgraphs in Triangle- Free Graphs with Maximum Degree Three

Combinatorics · math.CO · posed by J.A. Bondy, S. C. Locke · open

1 attempt · 1 machine check

Statement

Let G be a graph with maximum degree at most three. Suppose that G has an m-covering by 5-cycles, for some positive integer m. Then G is one of the seven graphs depicted in Figure 7.11.

Context

Candidate 2 of the open problems stated in "Largest Bipartite Subgraphs in Triangle- Free Graphs with Maximum Degree Three", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Let H1,…,H7H_1,\dots,H_7 denote the seven finite graphs in Bondy–Locke Figure 7.11. Interpreting the supplied statement literally: for a finite simple graph GG, an mm-covering by 5-cycles means that every edge of GG lies in exactly mm cycles of length 55 (equivalently here, in a chosen 5-cycle cover). The conjecture asserts:

    Δ(G)≤3,G has an m-covering by C5’s for some m≥1  ⟹  G≅Hi for some i.\Delta(G)\le 3,\quad G\text{ has an }m\text{-covering by }C_5\text{'s for some }m\ge1 \implies G\cong H_i\text{ for some }i.

    The text does not state that GG is connected.

    Result: The literal statement is false.

    Let

    M=max⁡1≤i≤7∣V(Hi)∣,r=M+1,M=\max_{1\le i\le 7}|V(H_i)|,\qquad r=M+1,

    and let

    G=⨆j=1rC5G=\bigsqcup_{j=1}^{r} C_5

    be the disjoint union of rr 5-cycles.

    Then Δ(G)=2≤3\Delta(G)=2\le3. Each component is a single 5-cycle, and no 5-cycle can use vertices from two different components. Hence every edge of GG lies in exactly one 5-cycle, so GG has a 11-covering by 5-cycles.

    But

    ∣V(G)∣=5r=5(M+1)>M,|V(G)|=5r=5(M+1)>M,

    so GG is not isomorphic to any of the seven fixed graphs H1,…,H7H_1,\dots,H_7. Thus the conjecture, as stated, is disproved.

    The defect is the missing connectedness/componentwise condition. A natural repair would be to assume GG connected, or to conclude that each nontrivial connected component is one of the seven graphs.

    Citation: No external result is needed for the counterexample. Original source: J. A. Bondy and S. C. Locke, “Largest bipartite subgraphs in triangle-free graphs with maximum degree three,” Journal of Graph Theory 10 (1986), 477–504.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The counterexample is rigorous against the conjecture as stated. A disjoint union of sufficiently many C5C_5's has maximum degree 22, has a 11-covering by 5-cycles, and cannot be isomorphic to any one of the seven fixed finite graphs in Figure 7.11 by vertex count. Thus the literal statement is false. If connectedness was intended implicitly, the argument would not address that stronger version, but it is absent from the supplied conjecture.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted resolution is a valid but purely formal counterexample to the literal wording: take many disjoint C5C_5's. This only exploits the absence of a connectedness/componentwise hypothesis and does not address the intended connected classification. It is routine and not publishable as a standalone combinatorics result.

      Literature check: I found no evidence that this exact “many disjoint C5C_5’s” objection has been recorded as a published correction or erratum. Searches for the exact phrases “m-covering by 5-cycles,” “m-covering” + “5-cycles,” “Bondy Locke m-covering,” “Figure 7.11” + Bondy + Locke, and the paper title did not reveal an existing resolution or stronger published counterexample. Available indexing/search traces point back only to the original Bondy–Locke article, not to later literature resolving this literal disconnected-graph issue.

      Citation: J. A. Bondy and S. C. Locke, “Largest bipartite subgraphs in triangle-free graphs with maximum degree three,” Journal of Graph Theory 10 (1986), 477–504.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.