Alphabeta Math
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.

Rooted block exposure and attachment separation

Statement

Let G be a finite connected simple graph with an edge. Its blocks are its maximal 2-connected subgraphs and its bridge edges with their endpoints; a cutvertex is a vertex whose deletion increases the number of connected components. Form the bipartite incidence tree whose nodes are the blocks and cutvertices, with a block adjacent to each cutvertex it contains. Choose a block as root, and process the block nodes in nondecreasing distance from it, breaking ties arbitrarily. The exposed vertices before a block is processed are the union of the vertex sets of the earlier blocks.

Each nonroot block B has a unique adjacent cutvertex on the path from B to the root, called its attachment vertex a. Every vertex of B other than a is unexposed before B is processed and has no neighbour among the previously exposed vertices except possibly a.

Facts & Assumptions

[F1]

For the stated graph, distinct blocks meet in at most one vertex, every common vertex is a cutvertex, every edge belongs to a block, and the block-cutvertex incidence graph is a tree. Block incidence tree and containment contract

[F2]

In a tree there is a unique path between any two nodes. Rooting it at a node gives each other node a unique predecessor on its path to the root; distance is the number of edges on that path. A nonempty simple graph is a tree if and only if each pair of vertices is joined by exactly one path

[F3]

Blocks and cutvertices have the meanings stated above, and a block is a subgraph: its edges have endpoints in its vertex set. Cutvertices, 2-connected pieces and nontrivial blocks Subgraphs, induced subgraphs and spanning subgraphs

Proof

Given: The graph, rooted incidence tree, and processing order in the statement; a nonroot block B with attachment vertex a.

Goal: Show that each x in V(B) other than a is new and has no earlier exposed neighbour other than possibly a.

1.1F1F2F3given

The predecessor of B is a cutvertex node because the incidence tree is bipartite; it is unique by the unique-path property. If a cutvertex x in B differs from a, its node is a child of B: its path to the root starts through B. Every other block containing x is then a child of x, so its distance from the root is two more than that of B. Indeed, any other direction would give a second path to the root. Thus a block other than B containing x is processed strictly later. If x is not a cutvertex, no other block contains it. Consequently no x in V(B) other than a is exposed earlier, including by a block on another branch.

2.1F1F2F3step 1.1∎

Let x be such a vertex and suppose xy is an edge with y in an earlier block D. Choose a block C containing xy. If C=B, then y belongs to both B and D; since D is earlier, step 1.1 forces y=a. If C differs from B, then x is a cutvertex and C is a child block of x, hence lies farther from the root than B. As x and y are distinct, the cutvertex node y, if it occurs in the incidence tree, cannot be the predecessor x of C. If D=C, then D is later than B, a contradiction. Otherwise y is a cutvertex shared by C and D; it is a child of C, and D is a child of y. Thus D is still farther from the root than C, contradicting its being earlier than B. The only possible earlier exposed neighbour is therefore a, as required.

Depends on

Used by · 1

Dependency tree · 2 levels

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. The view shows up to two dependency steps; open a prerequisite to continue.