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 labelled simple regular graph orders

Statement

For integers $n \geq 1$ and $d \geq 0$ , put $V = {1, \dots, n}$ and let $G_{d} (n)$ be the set of all graphs $(V, E)$ such that $E$ is a set of two-element subsets of $V$ and each vertex belongs to exactly $d$ edges. These are the labelled simple $d$ -regular graphs on $V$ ; this definition imposes no parity restriction on $n d$ . Then $G_{d} (n)$ is nonempty if and only if $d < n$ and $n d$ is even. Under these conditions the simplicity event $S$ in the uniform pairing model has strictly positive probability. No lower bound uniform in $n$ is asserted.

Statement references

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Pairings, simple-graph conditioning and model transfer

Facts & Assumptions

[F1]

A finite simple graph $(V, E)$ has a finite vertex set $V$ and an edge set consisting of two-element subsets of $V$ , with no loops or repeated edges (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets). The requirement that each vertex belongs to exactly $d$ edges defines $d$ -regularity here for every integer $d \geq 0$ .

[F2]

For $n \geq 1$ , $d \geq 0$ and $n d$ even, Pairings, simple-graph conditioning and model transfer defines the finite uniform pairing space, its collapse and its simplicity event $S$ ; each simple regular graph has exactly $(d!)^{n}$ pairing realizations. Every outcome of this nonempty finite uniform space has positive probability, including the unique empty pairing when $d = 0$ .

Proof

Given: Integers $n \geq 1$ and $d \geq 0$ and the graph set defined in the statement; the pairing model is invoked only after $n d$ is known to be even.

Goal: Prove feasibility and positivity of the simplicity event.

1.1F1givenalgebra

If $(V, E)$ belongs to $G_{d} (n)$ , its $d$ distinct neighbours at any vertex lie among the other $n - 1$ vertices. Counting the incidences $(v, e)$ with $v \in e \in E$ first by vertices and then by edges gives $n d = 2 ∣ E ∣$ , since every edge has two distinct endpoints. Thus $d < n$ and $n d$ is even.

1.2givenconstructalgebra

Conversely suppose $d < n$ and $n d$ is even. If $d = 2 k$ , put $D = {1, \dots, k} \cup {n - k, \dots, n - 1}$ , with both sets empty when $k = 0$ . Since $2 k < n$ , the two sets are disjoint subsets of ${1, \dots, n - 1}$ . If $d = 2 k + 1$ , then $n$ is even; put $D = {1, \dots, k} \cup {n - k, \dots, n - 1} \cup {n / 2}$ , again taking the first two sets empty when $k = 0$ . The inequality $2 k + 1 < n$ gives $k < n / 2$ , so the three sets are disjoint subsets of ${1, \dots, n - 1}$ . In either case $∣ D ∣ = d$ and $t \in D$ if and only if $n - t \in D$ .

1.3givenconstructalgebra

For $v \in V$ and an integer $1 \leq t \leq n - 1$ , define $c_{v} (t) = v + t$ when $v + t \leq n$ , and $c_{v} (t) = v + t - n$ when $v + t > n$ . These two explicit formulas give a vertex of $V$ different from $v$ . The map $t \mapsto c_{v} (t)$ is a bijection from ${1, \dots, n - 1}$ to $V ∖ {v}$ : for $w > v$ its unique inverse value is $t = w - v$ , and for $w < v$ it is $t = n + w - v$ , as is checked in the two branches. If $w = c_{v} (t)$ , the same formulas give $c_{w} (n - t) = v$ : when $v + t \leq n$ one has $w + n - t = v + n > n$ , and when $v + t > n$ one has $w + n - t = v \leq n$ . This defines and verifies the required cyclic operation using integer labels only.

2.1F1step 1.2step 1.3construct

Define $E = {{v, c_{v} (t)} : v \in V, t \in D}$ . It is a set of two-element subsets of $V$ , hence $(V, E)$ is simple by [F1]. At each $v$ the vertices $c_{v} (t)$ for $t \in D$ are distinct by step 1.3. Every edge incident to $v$ is of this form: an edge generated at some other vertex $w$ with $v = c_{w} (t)$ has $w = c_{v} (n - t)$ , and $n - t \in D$ by step 1.2. Thus the incident edges at $v$ are exactly ${v, c_{v} (t)}$ for $t \in D$ , and there are $∣ D ∣ = d$ of them. This constructs a member of $G_{d} (n)$ , including the empty edge set when $d = 0$ and in particular when $n = 1$ .

3.1F2step 1.1step 2.1algebra∎

Under the sufficient conditions, $n d$ is even, so [F2] applies to the constructed graph. It has $(d!)^{n} \geq 1$ pairing realizations. At least one outcome of the nonempty finite uniform pairing space therefore belongs to $S$ , and every such outcome has positive probability by [F2]. Consequently $P (S) > 0$ . Together with step 1.1 and step 2.1 this proves the equivalence and the asserted positivity, without asserting a uniform lower bound.

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.