ProbXiv
sign in

CYCLES IN THE COMPLEMENT OF A TREE OR OTHER GRAPH

Combinatorics · math.CO · posed by F.C. HOLROYD, W.J.G. WINGATE · open

1 attempt · 1 machine check

Statement

(i) If TT is a pp-tree, then θ(T)\theta(T) is single-valued if p≥6p \ge 6. (ii) If TT is a pp-tree, then for each p≥7p \ge 7: θ(T)={p−2ifΔ(T)⩾p−3,p−1otherwise.\theta(T)=\left\{\begin{array}{ll}p-2&\text{if}\Delta(T)\geqslant p-3,\\p-1&\text{otherwise.}\end{array}\right.

Context

Candidate 3 of the open problems stated in "CYCLES IN THE COMPLEMENT OF A TREE OR OTHER GRAPH", 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 TT be a finite simple tree on pp vertices, T‾\overline T its complement, γ(T,m)\gamma(T,m) the number of simple mm-cycles in T‾\overline T, and

    θ(T)={m∈{3,…,p}:γ(T,m)=max⁡rγ(T,r)}.\theta(T)=\{m\in\{3,\dots,p\}:\gamma(T,m)=\max_r\gamma(T,r)\}.

    The conjecture asserts that for p≥6p\ge6, θ(T)\theta(T) is a singleton, and for p≥7p\ge7,

    θ(T)={{p−2},Δ(T)≥p−3,{p−1},Δ(T)<p−3.\theta(T)= \begin{cases} \{p-2\},& \Delta(T)\ge p-3,\\ \{p-1\},& \Delta(T)<p-3. \end{cases}

    Result: The stated conjecture is false.

    Take p=8p=8, and let TT be the double-star with adjacent central vertices x,yx,y, three leaves adjacent to xx, and three leaves adjacent to yy. Then

    Δ(T)=4<5=p−3,\Delta(T)=4<5=p-3,

    so the conjecture predicts θ(T)={7}\theta(T)=\{7\}.

    Counting cycles in T‾\overline T by inclusion-exclusion over the forbidden tree edges gives:

    m345678γ(T,m)2669144222216108.\begin{array}{c|cccccc} m&3&4&5&6&7&8\\ \hline \gamma(T,m)&26&69&144&222&216&108. \end{array}

    Thus the unique maximum occurs at m=6m=6, not at m=7m=7. Hence

    θ(T)={6}={p−2}≠{p−1},\theta(T)=\{6\}=\{p-2\}\ne\{p-1\},

    contradicting part (ii).

    For verification, the relevant linear-forest counts in TT are

    L0,0=1, L1,1=7, L2,1=12, L2,2=9, L3,1=9, L3,2=18, L4,2=9,L_{0,0}=1,\ L_{1,1}=7,\ L_{2,1}=12,\ L_{2,2}=9,\ L_{3,1}=9,\ L_{3,2}=18,\ L_{4,2}=9,

    and substituting these into the standard inclusion-exclusion formula for mm-cycles in a graph complement yields the displayed table.

    Citation: No external disproof is used here. Original source: F. C. Holroyd and W. J. G. Wingate, “Cycles in the complement of a tree or other graph,” Discrete Mathematics 55 (1985), 267–282.

    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 valid. For the 8-vertex double-star, Δ(T)=4<5=p−3\Delta(T)=4<5=p-3, so the conjecture predicts θ(T)={7}\theta(T)=\{7\}. The displayed cycle counts in T‾\overline T are correct:

      (26,69,144,222,216,108)(26,69,144,222,216,108)

      for lengths 3,…,83,\dots,8, with unique maximum at m=6m=6. Hence θ(T)={6}\theta(T)=\{6\}, contradicting part (ii) of the conjecture.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted resolution is a valid small counterexample to Holroyd–Wingate Conjecture 3(ii). If not previously recorded, it is genuinely new, but its significance is minor: it is an 8-vertex explicit computation, not a structural theorem or corrected classification. On its own it would likely be an erratum/short note rather than a standalone standard-journal paper.

      Literature check: I found related work on total numbers of cycles in complements of trees, especially Zhou’s 1988 paper resolving Holroyd–Wingate/Reid extremal questions, and Alameddine’s follow-up “From paths to stars.” I also checked searches around the exact paper title/authors, “Conjecture 3,” θ(T)\theta(T), the Δ(T)≥p−3\Delta(T)\ge p-3 criterion, double-stars, and the numerical cycle-count vector 26,69,144,222,216,10826,69,144,222,216,108, including OEIS entries citing Holroyd–Wingate for complete/path complements. None located this specific counterexample or a stronger published refutation of the θ(T)\theta(T) conjecture.

      Citation: F. C. Holroyd and W. J. G. Wingate, “Cycles in the complement of a tree or other graph,” Discrete Mathematics 55 (1985), 267–282. Related: B. Zhou, “The maximum number of cycles in the complement of a tree,” Discrete Mathematics 69 (1988), 85–94.

      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.