gpt 6 astra ultra attempt on Math-1113

Cycles in Graphs of Large Chromatic Number

Definitions and mathematical statement

Let $G$ be a finite simple undirected graph and let $k\ge3$ be an integer. The chromatic number $\chi(G)$ is the least number of colours in a proper vertex colouring. A cycle means a simple cycle, with no repeated vertex except the equality of its initial and final vertex. Its length is its number of edges. Count cycles as distinct subgraphs, without distinguishing a starting vertex or a direction of traversal; chords between vertices of a cycle are permitted.

Let $c_{0,k}(G)$ count the cycles whose lengths are positive multiples of $k$. The intended conjecture is \[ \chi(G)>k\quad\Longrightarrow\quad c_{0,k}(G)\ge\frac{(k+1)(k-1)!}{2}. \] The bound counts cycles individually, with no requirement of edge or vertex disjointness. In $K_{k+1}$ the only possible positive multiple of $k$ among cycle lengths is $k$. Choosing the omitted vertex and a cyclic ordering of the others gives exactly $(k+1)(k-1)!/2$ such cycles, explaining the proposed extremal quantity.

The restriction $k\ge3$ is essential and is stated explicitly in the primary formulation [S3]. It is missing from the imported one-sentence statement. Without it the assertion fails: $K_3$ is more than 2-chromatic but has no even cycle, and a nontrivial tree is more than 1-chromatic but has no cycle. The present expansion restores this published parameter range rather than treating those trivial failures as the intended problem.

Short English statement

Does every graph needing more than k colours contain at least as many cycles of length divisible by k as the complete graph on k+1 vertices, for k at least three?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 2 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature and counting convention.

The source attributes this conjecture to Brewster, McGuinness, Moore and Noel. The primary paper [S3], checked again for this attempt, proves the full case $k=3$. It also proves additional results under criticality and minimum-degree hypotheses. We do not assume that a critical graph has minimum degree exactly $k$: only a lower bound follows automatically. The following argument establishes the required count for an infinite family having chromatic number $k+1$ but no $K_{k+1}$. Each cycle is counted up to rotation and reversal, as in the definition.

A critical reduction and the clique benchmark.

If $\chi(G)>k$, choose an induced subgraph $H$ minimal by vertex deletion with this property. Deleting any vertex leaves a $k$-colourable graph, and restoring it with a fresh colour shows $\chi(H)=k+1$. Every vertex of $H$ has degree at least $k$: otherwise a $k$-colouring of its deletion extends by an unused colour. Since every cycle of $H$ is also a cycle of $G$, it would suffice to prove the target for these critical graphs. This reduction does not bound their orders.

If $G$ contains $K_{k+1}$, each choice of $k$ vertices supports $(k-1)!/2$ distinct cycles of length $k$. Different choices have different vertex sets, giving exactly the proposed lower bound from that clique. The reduction therefore leaves particular interest in critical graphs without a clique of order $k+1$.

A nonclique family meeting the required count.

Fix an odd integer $\ell\ge\max(5,k+1)$ and form the join \[ H=K_{k-2}+C_\ell. \] A join retains the two graphs and adds every edge between them. Colours used on its two sides must be disjoint. Since an odd cycle needs three colours, $\chi(H)=(k-2)+3=k+1$. Its clique number is $k$, because a cycle of length at least five has clique number two; in particular this family is not covered by the preceding $K_{k+1}$ argument.

For each edge $uv$ of the cycle, take $u,v$ together with all $k-2$ vertices on the complete side. These $k$ vertices induce a $K_k$, which has $(k-1)!/2$ Hamilton cycles. The justification is to fix one starting vertex, order the remaining $k-1$ vertices, and identify the two orientations of each cycle. The identification has no fixed point because $k\ge3$. Cycles obtained from different rim edges have different vertex sets, so none is counted twice. Consequently \[ c_{0,k}(H)\ \ge\ \ell\frac{(k-1)!}{2} \ \ge\ \frac{(k+1)(k-1)!}{2}. \] There may be many further cycles; the argument needs only these length-$k$ witnesses. For $k=3$ this specializes to the odd wheel, whose rim edges give distinct triangles through the centre. For every $k$ it works for arbitrarily large odd $\ell$.

Verification and limits of a subdivision approach.

The finite certificate [R1] constructs the joins with $(k,\ell)=(3,5),(4,5),(5,7),(6,7)$ and enumerates their simple length-$k$ cycles, identifying rotations and reversal. It checks the lower count and the absence of a clique of order $k+1$. This verifies the counting conventions on small representatives; the displayed proof establishes the entire family.

Trying to replace the actual clique by a subdivided clique loses the argument: subdivision changes cycle lengths and their residues modulo $k$. It also need not preserve the relevant chromatic obstruction. For example, subdividing every edge once makes any graph bipartite, by separating original vertices from subdivision vertices. Thus the existence of a topological clique alone gives neither the required chromatic reduction nor the correct divisibility count. Likewise, the critical reduction only yields $\delta(H)\ge k$, not equality; a theorem requiring a vertex of degree $k$ needs an additional argument.

Final status and first remaining gap.

UNRESOLVED. The known full $k=3$ theorem is acknowledged, and an explicit clique-free-at-order-$k+1$ join family is proved to satisfy the bound for every $k\ge3$. For general $k\ge4$, no argument here produces the required number of distinct divisible-length cycles in arbitrary critical graphs. Controlling that count outside the join construction is the first remaining gap.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3254 (OPG-60001), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Cycles in Graphs of Large Chromatic Number. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/cycles_in_graphs_of_large_chromatic_number.
• S3 S. Kim and M. E. Picollelli, 4-Chromatic Graphs Have At Least 4 Cycles of Length 0 mod 3 $2023$, abstract explicitly states k at least 3. https://arxiv.org/abs/2312.05945.

• R1 Reproducible finite checks, using Python's standard library: scripts/check_attempt_batch03_colouring_2026_10_02.py, section 3254. The source [S3] was checked on 2 October 2026 for the stated literature result.