Alphabeta Math
LemmaStatement: AI-generatedProof: AI-generated
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The finite graph boundary gives two-uniform witnesses

Statement

For integers q≥3 and k≥1 there is a finite 2-uniform hypergraph of Berge girth at least q with no weak k-colouring.

Facts & Assumptions

[F1]

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets defines finite simple graphs, r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s defines 2-uniform hypergraphs, and Berge cycles, incidence graphs and girth and Weak hypergraph colourings with singleton boundary define Berge cycles and weak colourings.

[F2]

Erdős, Graph theory and probability, p.35, supplies a finite simple graph with no circuit shorter than q and chromatic number greater than k; see External input.

[F3]

Proper vertex colourings and chromatic number defines proper graph colourings and χ(G) using the natural-number palette k={0,…,k−1}. Relabelling colours by a bijection preserves properness.

[F4]

Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges defines an ordinary graph cycle as a closed walk of length at least three with distinct vertices apart from its coinciding endpoints. These are the closed circuits in the imported result: Erdős, p.36, displays the cyclic edge sequence and counts ordered choices of distinct circuit vertices.

Proof

Given: The hypotheses of the statement.

Goal: Its asserted conclusion.

1.1F1F2F3construct

Apply F2 to obtain a finite graph G and regard its edge set as a set of two-element hyperedges on V(G). On such an edge the weak-colouring condition is exactly that its two endpoints have different colours. The bijection j↦j−1 from [k]={1,…,k} to {0,…,k−1} converts a weak k-colouring into a proper graph k-colouring in F3; its inverse j↦j+1 gives the converse. Thus such a weak colouring would imply χ(G)≤k, contrary to F2.

2.1F1F2F4step 1.1∎

A Berge cycle of length two would require two distinct two-element edges containing the same two distinct vertices, impossible in a simple graph. In a Berge cycle of length t≥3, edge ei contains the two distinct vertices xi−1,xi and therefore equals their pair, with indices modulo t. Hence (x0,x1,…,xt−1,x0) is an ordinary graph cycle of length t in F4: its consecutive edges are e1,…,et−1,e0, and the Berge vertices are distinct. F2 excludes every such cycle with t<q, proving the Berge girth assertion for the hypergraph in step 1.1.

External input

The following established result is used as an external premise, rather than claimed as a locally reconstructed proof: For each prescribed integer q≥3 there exist finite graphs with arbitrarily large chromatic number and no closed circuit with fewer than q edges. More precisely, the p.35 paragraph asserts an n-vertex graph of chromatic number greater than nc for a positive constant c (with q fixed) and with no closed circuit of fewer than q edges.

Source notes

Read the full five-page original PDF text and inspected rendered printed pp.35–36: p.35 gives the finite n-vertex high-chromatic assertion and its strict circuit threshold; p.36 writes a circuit as cyclic edges on distinct ordered vertices. The definition of h(k,l), equation (4) and its proof were read in the PDF text. Only the finite high-girth/high-chromatic existence consequence and this circuit convention are used; the probabilistic estimates were not independently audited.

Depends on

Used by · 1

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.

External dependencies

P. Erdős, Graph theory and probability, Canadian Journal of Mathematics 11 (1959), 34–38 · Printed p.35 (PDF p.2), paragraph following equation (5), beginning “Now (4) clearly shows”; p.36, paragraph displaying a given closed circuit and counting its distinct ordered vertices; definition of h(k,l) and equation (4) on p.34; proof of (4), pp.35–37

For each prescribed integer q≥3 there exist finite graphs with arbitrarily large chromatic number and no closed circuit with fewer than q edges. More precisely, the p.35 paragraph asserts an n-vertex graph of chromatic number greater than n^c for a positive constant c (with q fixed) and with no closed circuit of fewer than q edges.

Hypotheses: Fixed finite circuit threshold q≥3; n sufficiently large. Graphs are finite simple graphs; chromatic number refers to proper vertex colouring.

Reading limits: Read the full five-page original PDF text and inspected rendered printed pp.35–36: p.35 gives the finite n-vertex high-chromatic assertion and its strict circuit threshold; p.36 writes a circuit as cyclic edges on distinct ordered vertices. The definition of h(k,l), equation (4) and its proof were read in the PDF text. Only the finite high-girth/high-chromatic existence consequence and this circuit convention are used; the probabilistic estimates were not independently audited.

Sources