Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26
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 Cayley graph is connected if and only if the subset generates the group

Statement

A Cayley graph is connected if and only if the subset generates the group.

Facts & Assumptions

Given: The hypotheses of the Statement.

[F1]

The Cayley graph of a group G with respect to a subset S has vertex set G and edge set {{g,gs}:g∈G, s∈(S∪S−1)∖{e}} (The Cayley graph of a group with respect to a subset).

[F2]

A walk of length ℓ in a simple graph is a finite vertex list (v0,…,vℓ) with consecutive vertices adjacent; a path is a walk with distinct vertices; the graph is connected when it is nonempty and every two vertices are joined by a path (Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set).

[L1]

⟨S⟩  :=  ⋂{ H  :  H≤G and S⊆H }. (The subgroup ⟨S⟩ generated by a subset, the cyclic subgroup ⟨g⟩, and cyclic groups).

[L2]

An elementary cancellation deletes two adjacent letters xx−1 or x−1x. A word is reduced if no elementary cancellation applies. (Words in an alphabet with formal inverses, elementary cancellation, and reduced words).

Proof

technique · direct
1.1F1F2L1L2

A walk from the identity to g spells an expression for g as a product of elements of S and their inverses, and each such expression is a walk.

2.1F1F2L1step 1.1∎

So the component of the identity is exactly the generated subgroup, and left translation carries it onto the component of any vertex; connectedness therefore means the subgroup is everything.

Depends on

Used by

Dependency tree · two levels

13 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