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.
Block containment and monotonicity under subgraphs
Statement
Every 2-connected subgraph of a finite simple graph is contained in a maximal 2-connected subgraph. If nonempty finite simple graphs and admit an ordinary embedding of in , then . In particular, a 2-connected graph with more than vertices cannot occur as a subgraph of .
Here 2-connected means having at least three vertices, being connected, and remaining connected after deletion of any one vertex. Maximality is with respect to subgraph containment. The nontrivial blocks of a graph are its maximal 2-connected subgraphs and its bridge-edge subgraphs; a bridge is an edge whose deletion increases the number of connected components. For a nonempty graph with an edge, is the largest order, meaning number of vertices, of a nontrivial block; for an edgeless nonempty graph it is . An ordinary embedding is an injective vertex map that preserves edges, with extra edges allowed in the target.
Statement references
Facts & Assumptions
A finite simple graph has finitely many subgraphs; its edges have two distinct endpoints. A subgraph has subsets of the ambient graph's vertices and edges. Subgraphs, induced subgraphs and spanning subgraphs Cutvertices, 2-connected pieces and nontrivial blocks
An ordinary embedding is an isomorphism onto the subgraph formed by its image vertices and image edges. Ordinary embeddings as injections preserving edges
Vertices lie in the same component exactly when a path joins them. A simple cycle has at least three distinct vertices and deleting any vertex leaves a connected path on the remaining vertices. Deleting an edge removes that edge, while deleting a vertex also removes its incident edges. Connected graphs and connected components defined by the existence of vertex paths Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
A bridge is an edge whose deletion increases the component count. The nontrivial blocks and the parameter have the meanings stated above; their finite maximum exists when there is an edge. A bridge as an edge whose deletion increases the number of connected components Cutvertices, 2-connected pieces and nontrivial blocks The cardinality | A| of a finite set
Proof
Given: A finite simple graph , and, for the monotonicity claim, a nonempty finite simple graph with an ordinary embedding into nonempty .
Goal: Establish maximal containment and the stated inequalities.
Let be a 2-connected subgraph of . The finite, nonempty family of 2-connected subgraphs of containing has a member maximal under subgraph containment: otherwise a strictly increasing chain could be extended indefinitely within that finite family. Any 2-connected subgraph properly containing would also contain , so is maximal among all 2-connected subgraphs of .
Every edge of lies in a nontrivial block. If is a bridge, its endpoint subgraph is such a block. Otherwise and remain in the same component of : if they were in different components, adding back would merge exactly their two components and deletion of would increase the component count. A path from to in , together with , forms a simple cycle. This cycle is 2-connected, so step 1.1 puts it, and hence , in a maximal 2-connected subgraph of .
If is edgeless, then : the right side is when is edgeless and at least otherwise, by step 2.1. Suppose instead that has an edge, and choose a nontrivial block of order . If is 2-connected, its image under is a 2-connected subgraph of : the isomorphism preserves paths and vertex deletion, so connectivity and connectivity after each vertex deletion are preserved. By step 1.1 its image lies in a nontrivial block of . If is a bridge-edge subgraph of , its image edge lies in a nontrivial block of by step 2.1, whether or not that image edge is a bridge in . In either case injectivity gives , proving .
If a 2-connected graph occurs as a subgraph of , step 1.1 contains it in a maximal 2-connected subgraph of . Its order is therefore at most , proving the final assertion.
Depends on
- Cutvertices, 2-connected pieces and nontrivial blocks
- Ordinary embeddings as injections preserving edges
- Subgraphs, induced subgraphs and spanning subgraphs
- A bridge as an edge whose deletion increases the number of connected components
- The cardinality | A| of a finite set
- Connected graphs and connected components defined by the existence of vertex paths
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
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.