TheoremStatement: Literature-sourcedProof: AI-adaptedverified 2026-09-26 (gpt-6-sol)

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.

The Cayley graph of a free group with respect to a free basis is a tree

Statement

The Cayley graph of a free group with respect to a free basis is a tree.

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, g s} : g \in G, s \in (S \cup S^{- 1}) ∖ {e}}$ (The Cayley graph of a group with respect to a subset).

[L1]

A Cayley graph is connected if and only if its defining subset generates the group (A Cayley graph is connected if and only if the subset generates the group).

[L2]

A cycle is a closed walk of length at least three with distinct vertices apart from its endpoints; a forest is a simple graph with no cycle and a tree is a connected forest (Cycles, trees and forests in a simple graph on an arbitrary vertex set).

[L3]

A simple graph is a tree if and only if every two of its vertices are joined by exactly one path (A nonempty simple graph is a tree if and only if each pair of vertices is joined by exactly one path).

[L4]

A free group on a set $X$ is a group $F (X)$ together with a map $i : X \to F (X)$ such that, for every group $G$ and every function $u : X \to G$ , there is a unique group homomorphism $\hat{u} : F (X) \to G$ satisfying (Free group on a set of generators).

[L5]

The subset $B$ is a free basis of $F$ if $(F, i)$ is a free group on the set $B$ in the sense of. (A free basis of a group).

[L6]

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

[L7]

The reduced words on $X ⊔ X^{- 1}$ form a group when the product of reduced words is their concatenation followed by free reduction. (Reduced words form the free group on an alphabet).

[L8]

Every class in $W (X) / \sim$ contains exactly one reduced word. (Every class in $W (X) / \sim$ contains exactly one reduced word).

Proof

technique · contradiction

1.1F1L1L4L5

A free basis generates, so the Cayley graph is connected.

1.2F1L2L6L7assume-contra

Suppose it contains a cycle $g_{0}, \dots, g_{n - 1}$ of length $n \geq 3$ , with $g_{n} = g_{0}$ . On each right Cayley edge, the quotient $g_{j}^{- 1} g_{j + 1}$ is a basis letter or its inverse. No two consecutive labels cancel, including the last and first: such cancellation would immediately return to the preceding vertex, contrary to the distinct vertices in a simple cycle. Thus the cyclic sequence of edge labels is a nonempty reduced word.

2.1L2L8step 1.1step 1.2discharge-contradiction∎

The product of its labels telescopes to $g_{0}^{- 1} g_{n} = e$ . A nonempty reduced word cannot represent the identity by uniqueness of normal form, a contradiction. The graph is connected and has no cycle, hence is a tree.

Depends on

Used by

Dependency tree · two levels

22 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

C. Loh, Geometric Group Theory: An Introduction (2015 course version), 264 pp. (standard reference, not scraped)
C. Drutu and M. Kapovich, Geometric Group Theory (with an appendix by B. Nica), 837 pp. (standard reference, not scraped)