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.

Feasible orders for labelled simple regular graphs

Statement

For integers $n \geq 1$ and $d \geq 0$ , a labelled simple $d$ -regular graph on $[n] = {1, \dots, n}$ exists exactly when $d < n$ and $n d$ is even. For fixed $d$ , these orders form an unbounded set; for odd $d$ they are precisely the even $n > d$ .

Facts & Assumptions

[F1]

Pairings, simple-graph conditioning and model transfer defines labelled simple regular graphs and their uniform law whenever the graph set is nonempty.

[F2]

Asymptotic quantifiers and uniform parameter ranges defines feasible-order limits and records the necessary degree and parity restrictions.

[F3]

For n ≥ 1 the congruence classes modulo n form an abelian group (ℤ/n, +) of order n, generated by the class of 1 supplies, for $n \geq 1$ , the additive group of congruence classes modulo $n$ , with well-defined addition $[a] + [b] = [a + b]$ and unique representatives $0, \dots, n - 1$ .

Proof

Given: The objects and hypotheses in the Statement.

Goal: Establish every assertion of the Statement.

1.1F1F2

Each vertex has at most $n - 1$ neighbors, so $d < n$ . Counting incidences of edges with vertices gives $n d = 2 ∣ E ∣$ , hence $n d$ is even.

2.1F1F3step 1.1construct∎

Conversely work in the additive group $Z / n$ supplied by F3, writing $j$ for a residue class and translating its unique representative $r \in {0, \dots, n - 1}$ to label $r + 1$ . If $d = 2 k$ is even, join $j$ to $j \pm 1, \dots, j \pm k$ . Since $2 k < n$ , these are $2 k$ distinct nonzero residues relative to $j$ , and adjacency is symmetric; this is a simple $d$ -regular graph. It includes the empty-edge graph when $k = 0$ . If $d = 2 k + 1$ is odd, parity forces $n$ even. Use the same $2 k$ neighbors and add $j + n / 2$ ; because $2 k + 1 < n$ , this residue is distinct from all previous neighbors and from $j$ . The added edges are symmetric. Every vertex has exactly $d$ neighbors. Relabeling gives the claimed graph on $[n]$ . Arbitrarily large even $n > d$ satisfy these conditions for every fixed $d$ .

Depends on

Used by · 2

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.