Alphabeta MathHow 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 belongs to exactly one nontrivial block
Statement
In a finite connected simple graph with an edge, every edge belongs to exactly one nontrivial block.
Facts & Assumptions
Nontrivial blocks are maximal 2-connected subgraphs and bridge endpoint subgraphs. In a 2-connected graph deletion of any vertex leaves a connected graph with at least two vertices. Cutvertices, 2-connected pieces and nontrivial blocks
Paths join vertices in a connected graph, deletion removes the specified vertices or edges, and a bridge is an edge whose deletion disconnects its component. Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges Connected graphs and connected components defined by the existence of vertex paths Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors A bridge as an edge whose deletion increases the number of connected components
Two 2-connected subgraphs sharing two vertices have 2-connected union, and every 2-connected subgraph has a maximal 2-connected extension in a finite graph. Union closure for overlapping 2-connected subgraphs Finite maximal extension of a 2-connected subgraph
Every nonbridge edge of a finite connected simple graph lies on a 2-connected cycle. Nonbridge edges lie on 2-connected cycles
A finite simple graph has a finite vertex set and an edge set of two-element subsets of it, so each edge has two distinct endpoints. A subgraph has a subset of the ambient vertices and a subset of the ambient edges, with both endpoints of every retained edge retained. A finite simple graph is a finite vertex set together with a set of two-element vertex subsets Subgraphs, induced subgraphs and spanning subgraphs
Proof
Given: The graphs and hypotheses in the Statement.
Goal: The asserted conclusion.
No edge of a 2-connected subgraph can be a bridge of the ambient graph. Indeed has a neighbor in distinct from : otherwise deleting isolates from a third vertex. A path from to in , preceded by , is a path from to avoiding . Any path using can replace it by this alternative walk; erasing portions between repeated vertices gives a path. Deleting therefore cannot disconnect any pair formerly joined.
If an edge is a bridge, its endpoint subgraph is a nontrivial block and step 1.1 excludes every 2-connected block containing it; no other bridge endpoint subgraph contains that edge. If it is not a bridge, the cycle lemma and maximal-extension lemma place it in a maximal 2-connected block. Two such blocks containing it share both endpoints; their 2-connected union forces them to coincide by maximality. Thus each edge belongs to exactly one block.
Depends on
- Cutvertices, 2-connected pieces and nontrivial blocks
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- Connected graphs and connected components defined by the existence of vertex paths
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
- A bridge as an edge whose deletion increases the number of connected components
- Union closure for overlapping 2-connected subgraphs
- Finite maximal extension of a 2-connected subgraph
- Nonbridge edges lie on 2-connected cycles
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Subgraphs, induced subgraphs and spanning subgraphs
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.