TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-13

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.

For all positive $k, ℓ$ , some finite graph has girth greater than $ℓ$ and chromatic number greater than $k$

Statement

For every pair of positive natural numbers $k, ℓ$ , there is a finite simple graph whose girth is greater than $ℓ$ and whose chromatic number is greater than $k$ .

Facts & Assumptions

Given: Positive naturals $k, ℓ$ .

[L1]

Girth and chromatic number have their finite-graph definitions; a forest has infinite girth, and in $K_{m}$ every two distinct vertices are adjacent (Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention, Proper vertex colourings and chromatic number, Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[L2]

Deleting vertices produces an induced subgraph and cannot create a cycle (Subgraphs, induced subgraphs and spanning subgraphs).

[L3]

The expected short-cycle count and the independence-number probability obey the bounds in The expected number of cycles of length at most $ℓ$ in $G (n, p)$ and $P (α (G (n, p)) \geq s) \leq (\binom{n}{s}) (1 - p)^{(\binom{s}{2})} \leq n^{s} \exp (- p (\binom{s}{2}))$ for $s \leq n$ .

[L4]

Markov bounds upper tails of nonnegative variables, the union bound controls finite unions, complements have complementary probabilities, and positive probability gives a witness (Markov's inequality on a finite probability space, The finite union bound, Normalization, nonnegativity, monotonicity, complements, and differences in a finite probability space, An event of positive probability in a finite probability space is nonempty).

[L5]

Deleting at most one vertex per listed defect leaves a repaired object of size bounded below as in the alteration method (The deletion-alteration method converts an expected defect count into a deterministic lower bound).

[L6]

Real-power laws hold and $\log n$ grows more slowly than every positive power of $n$ (The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents, The logarithm grows more slowly than every positive real power).

[L7]

$1 + x \leq \exp (x)$ , the exponential is strictly increasing and positive, and $\exp (- x) = 1 / \exp (x)$ ( $1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$ , The exponential function is strictly increasing, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ ).

Proof

technique · constructive

1.1

If $ℓ \leq 2$ , take $K_{k + 1}$ . It has no cycle of length at most $2$ . Every proper colouring gives distinct colours to its pairwise adjacent vertices, while assigning one colour per vertex is proper, so its chromatic number is $k + 1$ ; its girth is therefore greater than $ℓ$ .

L1construct

1.2

For the remaining range $ℓ \geq 3$ , choose a sufficiently large natural $n$ divisible by $2 k$ , put $s = n / (2 k)$ , and put $p = n^{- 1 + 1 / (2 ℓ)}$ .

givenchoose

2.1

By [L3] and the real-power laws, $E [X_{\leq ℓ}] \leq \sum_{r = 3}^{ℓ} n^{r / (2 ℓ)} / (2 r)$ , which is less than $n / 4$ for all sufficiently large $n$ . Markov then gives $P (X_{\leq ℓ} \geq n / 2) < 1 / 2$ .

step 1.2L3L4L6

2.2

Enlarge $n$ so that $s \geq 2$ and $\log n < n^{1 / (2 ℓ)} / (16 k)$ . Then $(\binom{s}{2}) \geq s^{2} / 4$ , so $p (\binom{s}{2}) \geq n^{1 + 1 / (2 ℓ)} / (16 k^{2})$ , whereas $s \log n < n^{1 + 1 / (2 ℓ)} / (32 k^{2})$ . Thus [L3] bounds $P (α (G (n, p)) \geq s)$ by an exponential whose exponent is less than $- n^{1 + 1 / (2 ℓ)} / (32 k^{2})$ . Enlarge $n$ once more so that this exponent is less than $- 1$ ; then [L7] gives a probability less than $\exp (- 1) = 1 / e \leq 1 / 2$ .

step 1.2L3L6L7algebra

3.1

Enlarge the choice of $n$ so both strict bounds hold. The union bound then gives positive probability that $X_{\leq ℓ} < n / 2$ and $α (G) < n / (2 k)$ simultaneously; fix such a graph.

step 2.1step 2.2L4choose

4.1

Delete one vertex from each cycle of length at most $ℓ$ . Fewer than $n / 2$ vertices are deleted, the induced survivor $H$ has more than $n / 2$ vertices, and [L2] gives girth greater than $ℓ$ .

step 3.1L2L5construct

5.1

If $H$ were $k$ -colourable, one colour class would have at least $∣ V (H) ∣ / k > n / (2 k)$ vertices and would be independent, contradicting $α (H) \leq α (G) < n / (2 k)$ . Thus $χ (H) > k$ .

step 3.1step 4.1L1algebra

6.1

Step 1.1 covers $ℓ \leq 2$ , while steps 1.2 through 5.1 cover $ℓ \geq 3$ , completing the construction.

step 1.1step 5.1discharge-construct∎

Depends on

Used by

A parameter ledger for the high-girth, high-chromatic alteration proof Example

Dependency tree · two levels

53 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

J. Matousek and J. Vondrak, The Probabilistic Method, Theorem 4.2.1 (standard reference, not scraped)
Y. Zhao, MIT 18.218 Probabilistic Method in Combinatorics, Theorem 6.3 (standard reference, not scraped)
M. Bucic, Probabilistic Method, Theorem 4.1 (standard reference, not scraped)

For all positive k,ℓk,ℓ, some finite graph has girth greater than ℓℓ and chromatic number greater than kk