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.

Reversible labels for adjacency slots

Statement

Let $A$ be the adjacency-slot matrix of a finite $d$ -regular multigraph in Regular multigraph and normalized adjacency. There is a finite set $S$ of directed slot labels, maps $o, t : S \to V$ (origin and terminal vertex), and an involution $s \mapsto \overset{ˉ}{s}$ such that $o (\overset{ˉ}{s}) = t (s)$ , $t (\overset{ˉ}{s}) = o (s)$ , and exactly $A_{x y}$ labels have origin $x$ and terminal vertex $y$ . Each vertex has $d$ outgoing labels. Diagonal labels may be fixed by the involution. A labelled walk of length $m$ is a list $(s_{1}, \dots, s_{m})$ with $t (s_{i}) = o (s_{i + 1})$ ; it starts at $o (s_{1})$ and is closed when $t (s_{m}) = o (s_{1})$ . The length-zero walk at a specified vertex is also allowed.

Facts & Assumptions

Given: The objects and hypotheses in the statement.

Goal: Establish every assertion in the statement.

[F1]

The adjacency-slot convention gives a symmetric nonnegative integer matrix with row sum $d$ , including arbitrary nonnegative diagonal entries (Regular multigraph and normalized adjacency).

Proof

1.1F1constructalgebra

For each unordered pair of distinct vertices ${x, y}$ , choose $A_{x y} = A_{y x}$ paired labels, one in each direction, and interchange each pair under reversal. For each $x$ , choose $A_{x x}$ distinct labels with both endpoints $x$ and fix each under reversal. This gives the required involution and endpoint counts; summing the counts over destinations gives $d$ outgoing labels at each vertex. No parity of $A_{x x}$ is required.

2.1step 1.1construct∎

The endpoint conditions in the definition of a walk ensure that concatenating two successive labels is possible. Reversal of a label always starts at its former endpoint, including a fixed loop label. Thus the proposed walk and reversal operations are well-defined. They encode exactly the slot multiplicities in $A$ , rather than requiring an ordinary loop with two incidence slots. This proves the assertions.

Depends on

Regular multigraph and normalized adjacency

Used by · 3

Dependency tree · 1 level

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.