Alphabeta Math
LemmaStatement: AI-adaptedProof: 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.

The greedy set is independent and meets every block

PDF p. 3: Section 3, independent-set paragraph, final sentence

Statement

Let H be a finite connected simple graph with at least one edge, and run Greedy choice in the block-cutvertex tree with any permitted choices. A block means a maximal 2-connected subgraph or a bridge with its endpoints. The procedure chooses a root block and then processes the other blocks in nondecreasing distance from it in the block-cutvertex tree, with arbitrary tie order; each nonroot block has an attachment vertex on its path to the root.

At each nonroot block, a newly chosen vertex has no neighbour among vertices chosen earlier, except possibly its attachment vertex. The output I is independent, meaning that no two distinct vertices of I are adjacent, and I meets every block of H.

Facts & Assumptions

[F1]

The greedy procedure chooses one vertex in the root block. For a subsequent block with attachment vertex a, it chooses nothing if a is already chosen and otherwise adds a vertex of that block other than a. Choices can be made at every required stage, and there are finitely many stages. Greedy choice in the block-cutvertex tree

[F2]

For this rooted ordering, each vertex of a nonroot block other than its attachment vertex has no neighbour among the vertices of earlier blocks except possibly the attachment vertex. Rooted block exposure and attachment separation

[F3]

The block-cutvertex tree has block and cutvertex nodes joined by incidence; the attachment vertex is the cutvertex represented by the node immediately following the nonroot block node on its path to the root. Block-cutvertex tree terminology

[F4]

A set of vertices is independent exactly when no two distinct vertices in it are adjacent. Finite induction permits a property verified initially and preserved at each successive stage to hold after every stage. Order, size, complement and independence number The principle of mathematical induction

Proof

Given: The graph, rooted block ordering, and permitted choices in the statement.

Goal: Establish the asserted neighbour property and prove that the output is independent and meets every block.

1.1F1F2F3

Before a nonroot block B is processed, every previously chosen vertex lies in an earlier processed block: the root choice lies in the root block, and every later addition lies in the block being processed. If a vertex x is newly chosen in B, then x is different from the attachment vertex a. By the exposure property, x has no neighbour among vertices of earlier blocks except possibly a. Hence it has no earlier chosen neighbour except possibly a.

2.1F1F3F4step 1.1baseih

Induct over the processed blocks, maintaining that the chosen set is independent and meets every block already processed. After the root stage, the set has one vertex, so it is independent and meets the root block. At a later block B, if its attachment vertex a is already chosen, no vertex is added and B is met at a. Otherwise a vertex x of B other than a is added. By step 1.1, its only possible earlier chosen neighbour is a, which is not chosen; hence adding x preserves independence, and x meets B. No vertices are removed, so all earlier blocks remain met.

3.1F1F4step 2.1discharge-induction∎

The finite induction therefore gives both properties after all blocks have been processed. The resulting set is the output I, which is independent and meets every block of H.

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.

Sources