ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-08-28

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.

A Schreier coset graph and its spanning-tree basis

Example

Let $H$ be the kernel of the homomorphism $F (a, b) \to Z / 2 Z \times Z / 2 Z$ sending both $a$ and $b$ to the nontrivial element of the corresponding factor. Then the Schreier graph has four cosets

$H, H a, H b, H a b,$

and the non-tree edges of the rooted spanning tree

$H \overset{a}{\to} H a, H \overset{b}{\to} H b, H a \overset{b}{\to} H a b$

give the free basis

$a^{2}, b^{2}, a b^{2} a^{- 1}, a b a b^{- 1}, b a b^{- 1} a^{- 1} .$

Facts & Assumptions

Given: The subgroup $H$ above.

[L1]

The Schreier graph records cosets and labeled generator edges (The labeled Schreier coset graph of a subgroup of a free group).

[L2]

Rooted spanning trees correspond to Schreier systems (Rooted spanning trees and Schreier systems correspond).

[L3]

The nontrivial Schreier generators of such a tree form a free basis (Under the stated choice boundary, every subgroup of a free group is free with its nontrivial Schreier generators as a basis).

Verification

technique · direct

1.1L1givenconstruct

The quotient records only the parities of the exponent sums of $a$ and $b$ , so the four right cosets are exactly $H$ , $H a$ , $H b$ , and $H a b$ . The labeled Schreier graph therefore has $a$ -edges $H \leftrightarrow H a$ and $H b \leftrightarrow H a b$ , and $b$ -edges $H \leftrightarrow H b$ and $H a \leftrightarrow H a b$ .

2.1L2step 1.1algebra

The three displayed edges form a rooted spanning tree, so [L2] gives the corresponding Schreier system ${1, a, b, a b}$ . The five positive edges not in that tree yield the nontrivial generators $a^{2}$ , $b^{2}$ , $a b^{2} a^{- 1}$ , $a b a b^{- 1}$ , and $b a b^{- 1} a^{- 1}$ .

3.1L3step 2.1∎

By [L3], those five elements form a free basis of $H$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

12 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.