ProbXiv
sign in

Independent sets in n-vertex k-chromatic ℓ-connected graphs

Combinatorics · math.CO · posed by John Engbers, Lauren Keough, Taylor Short · open

1 attempt · 1 machine check

Statement

Let 2≤ℓ<k2\le\ell<k and n ≠5. If G is an n-vertex k-chromatic ℓ\ell -connected graph,then i(G)≤i(G∗).i(G)\leq i\left(G^{*}\right).

Context

Candidate 2 of the open problems stated in "Independent sets in nn-vertex kk-chromatic ℓ\ell-connected graphs", 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: Reconstructed statement: In finite simple graphs, let i(G)i(G) be the total number of independent vertex sets. For 2≤ℓ<k2\le \ell<k, define

    G∗=Kℓ∨(Kk−ℓ∪En−k).G^*=K_\ell\vee (K_{k-\ell}\cup E_{n-k}).

    Conjecture 5.2 asserts: if n≠5n\ne 5 and GG is an nn-vertex kk-chromatic ℓ\ell-connected graph, then

    i(G)≤i(G∗).i(G)\le i(G^*).

    Result: The conjecture is false.

    For any ℓ≥3\ell\ge 3, set

    k=ℓ+1,n=ℓ+3,k=\ell+1,\qquad n=\ell+3,

    and let

    G=Kℓ−2∨C5.G=K_{\ell-2}\vee C_5.

    Then n≥6n\ge 6, so n≠5n\ne 5, and 2≤ℓ<k2\le \ell<k.

    The chromatic number is

    χ(G)=χ(Kℓ−2)+χ(C5)=(ℓ−2)+3=ℓ+1=k.\chi(G)=\chi(K_{\ell-2})+\chi(C_5)=(\ell-2)+3=\ell+1=k.

    Also GG is ℓ\ell-connected: deleting fewer than ℓ\ell vertices either leaves a vertex of Kℓ−2K_{\ell-2}, which is adjacent to all remaining vertices, or deletes all of Kℓ−2K_{\ell-2}, in which case at most one vertex of C5C_5 is deleted, leaving a connected graph.

    Now

    i(G)=i(Kℓ−2)+i(C5)−1=(ℓ−1)+11−1=ℓ+9.i(G)=i(K_{\ell-2})+i(C_5)-1=(\ell-1)+11-1=\ell+9.

    But here

    G∗=Kℓ∨(K1∪E2)=Kℓ∨E3,G^*=K_\ell\vee (K_1\cup E_2)=K_\ell\vee E_3,

    so

    i(G∗)=i(Kℓ)+i(E3)−1=(ℓ+1)+8−1=ℓ+8.i(G^*)=i(K_\ell)+i(E_3)-1=(\ell+1)+8-1=\ell+8.

    Thus

    i(G)=ℓ+9>ℓ+8=i(G∗),i(G)=\ell+9>\ell+8=i(G^*),

    contradicting the conjecture.

    The excluded case n=5n=5 is only the ℓ=2\ell=2 member of this same family, namely C5C_5.

    Citation: Conjecture and notation are from Engbers–Keough–Short, “Independent Sets in nn-vertex kk-chromatic, ℓ\ell-connected graphs,” arXiv:1907.03913, Conjecture 5.2. The counterexample above is explicit.

    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 proposed family is a valid counterexample. For any ℓ≥3\ell\ge3, G=Kℓ−2∨C5G=K_{\ell-2}\vee C_5 has n=ℓ+3≠5n=\ell+3\ne5, k=ℓ+1k=\ell+1, is kk-chromatic, and is ℓ\ell-connected. The independent-set counts are correct:

      i(G)=i(Kℓ−2)+i(C5)−1=(ℓ−1)+11−1=ℓ+9,i(G)=i(K_{\ell-2})+i(C_5)-1=(\ell-1)+11-1=\ell+9,

      while

      G∗=Kℓ∨(K1∪E2)=Kℓ∨E3G^*=K_\ell\vee(K_1\cup E_2)=K_\ell\vee E_3

      has

      i(G∗)=(ℓ+1)+8−1=ℓ+8.i(G^*)=(\ell+1)+8-1=\ell+8.

      Thus i(G)>i(G∗)i(G)>i(G^*), directly disproving the stated conjecture. I found no fatal gap in the argument.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample appears genuinely new but very minor: it is a one-paragraph construction obtained by joining the already-exceptional C5C_5 example with a clique. It disproves the stated conjecture, but the method is routine and unlikely to support a standalone journal paper beyond perhaps an erratum/comment.

      Literature check: I searched for the exact conjecture and surrounding phrases (“Conjecture 5.2”, “nn-vertex kk-chromatic ℓ\ell-connected”, “independent sets”), the paper title/DOI/authors, “counterexample”, and the proposed construction Kℓ−2∨C5K_{\ell-2}\vee C_5. The results led back to the original ScienceDirect/Marquette/arXiv article and unrelated graph-theory material; I found no prior correction, note, or paper giving this counterexample or a stronger disproof.

      Citation: Original conjecture: John Engbers, Lauren Keough, Taylor Short, “Independent sets in nn-vertex kk-chromatic ℓ\ell-connected graphs,” Discrete Mathematics 344 (2021), 112495; arXiv:1907.03913.

      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.