Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-04 (gpt-5.6-sol-codex-subscription)
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.

Every edge of a spanning tree determines a fundamental cut, and every edge crossing it restores a spanning tree

Statement

Let T be a spanning tree of G and e∈E(T). The two components A,B of T−e determine the fundamental cut

δT(e):={xy∈E(G):x∈A, y∈B}.

For every f∈δT(e), the graph T−e+f is a spanning tree of G.

Facts & Assumptions

Given: A spanning tree T of G and e∈E(T).

[L1]

T−e has exactly two tree components (Deleting any edge of a tree separates it into exactly two tree components).

[F2]

A spanning tree contains every vertex of G (Spanning trees of a graph).

Proof

technique · direct
1.1

Let A,B be the vertex sets of the two components of T−e. They partition V(G).

L1F2
2.1

If f=xy crosses from A to B, then T−e+f is connected: paths inside A and B, together with f, join every pair of vertices.

step 1.1L1
2.2

It is acyclic: each side is acyclic, and a cycle using f would require a second edge between the two sides, but T−e+f has only f.

step 1.1L1
3.1

It is spanning by construction, so it is a spanning tree of G.

step 2.1step 2.2F2∎

Depends on

Used by

Dependency tree · two levels

7 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