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 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 is independent, meaning that no two distinct vertices of are adjacent, and meets every block of .
Facts & Assumptions
The greedy procedure chooses one vertex in the root block. For a subsequent block with attachment vertex , it chooses nothing if is already chosen and otherwise adds a vertex of that block other than . Choices can be made at every required stage, and there are finitely many stages. Greedy choice in the block-cutvertex tree
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
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
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.
Before a nonroot block 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 is newly chosen in , then is different from the attachment vertex . By the exposure property, has no neighbour among vertices of earlier blocks except possibly . Hence it has no earlier chosen neighbour except possibly .
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 , if its attachment vertex is already chosen, no vertex is added and is met at . Otherwise a vertex of other than is added. By step 1.1, its only possible earlier chosen neighbour is , which is not chosen; hence adding preserves independence, and meets . No vertices are removed, so all earlier blocks remain met.
The finite induction therefore gives both properties after all blocks have been processed. The resulting set is the output , which is independent and meets every block of .
Depends on
- Greedy choice in the block-cutvertex tree
- Block-cutvertex tree terminology
- Order, size, complement and independence number
- Rooted block exposure and attachment separation
- The principle of mathematical induction
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Connected graphs and connected components defined by the existence of vertex paths
- Subgraphs, induced subgraphs and spanning subgraphs
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
- Maria Axenovich and Patrick Schmitteckert, Non-isomorphic graphs have distinct vertex-Ramsey classes, arXiv:2610.03704v1 · PDF p. 3, Section 3, independent-set paragraph, final sentence