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 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 has a unique adjacent cutvertex on the path from to the root, called its attachment vertex . Every vertex of other than is unexposed before is processed and has no neighbour among the previously exposed vertices except possibly .
Statement references
Facts & Assumptions
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
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
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 with attachment vertex .
Goal: Show that each in other than is new and has no earlier exposed neighbour other than possibly .
The predecessor of is a cutvertex node because the incidence tree is bipartite; it is unique by the unique-path property. If a cutvertex in differs from , its node is a child of : its path to the root starts through . Every other block containing is then a child of , so its distance from the root is two more than that of . Indeed, any other direction would give a second path to the root. Thus a block other than containing is processed strictly later. If is not a cutvertex, no other block contains it. Consequently no in other than is exposed earlier, including by a block on another branch.
Let be such a vertex and suppose is an edge with in an earlier block . Choose a block containing . If , then belongs to both and ; since is earlier, step 1.1 forces . If differs from , then is a cutvertex and is a child block of , hence lies farther from the root than . As and are distinct, the cutvertex node , if it occurs in the incidence tree, cannot be the predecessor of . If , then is later than , a contradiction. Otherwise is a cutvertex shared by and ; it is a child of , and is a child of . Thus is still farther from the root than , contradicting its being earlier than . The only possible earlier exposed neighbour is therefore , as required.
Depends on
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.