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-hitting deletion lowers maximum block order
Statement
Let be a finite connected simple graph with an edge, and let meet the vertex set of every nontrivial block. If is nonempty, then . Independence of is not required.
A graph is 2-connected if it has at least three vertices, is connected, and remains connected after deletion of any one vertex. A nontrivial block is either a maximal 2-connected subgraph or the two-vertex subgraph consisting of a bridge and its endpoints; a bridge is an edge whose deletion increases the number of connected components. For a nonempty graph with an edge, is the largest number of vertices in a nontrivial block; for an edgeless nonempty graph, . The graph is obtained by deleting the vertices in and their incident edges.
Statement references
Cutvertices, 2-connected pieces and nontrivial blocks
Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
The cardinality | A| of a finite set
A bridge as an edge whose deletion increases the number of connected components
Cliques, independent sets, clique number and independence number
Facts & Assumptions
Every 2-connected subgraph of a finite simple graph is contained in a maximal 2-connected subgraph. Block containment and monotonicity under subgraphs
The block and conventions are those in the statement; in particular the maximum exists for a finite nonempty graph with an edge. Cutvertices, 2-connected pieces and nontrivial blocks The cardinality | A| of a finite set
Vertex deletion leaves a subgraph on the undeleted vertices. Edge deletion removes only the specified edge. Vertices in the same component are joined by a path, and a path has distinct vertices. Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors 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
A bridge is an edge whose deletion increases the number of components. A bridge as an edge whose deletion increases the number of connected components
If is finite and is a proper subset of , then is finite and : the subset inequality holds and equality would force . A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
A vertex set is independent when no two of its distinct vertices are adjacent. Cliques, independent sets, clique number and independence number
Proof
Given: A finite connected simple graph with an edge, a set meeting every nontrivial block of , and nonempty .
Goal: Prove .
Since has an edge, it has a nontrivial block and . If is edgeless, then , so assume that has an edge. Let be a nontrivial block of with .
If is 2-connected, it is a 2-connected subgraph of , hence lies in a maximal 2-connected subgraph of . The set meets , while is disjoint from . Thus is a proper subset of the finite set , and .
Otherwise consists of a bridge edge of and its endpoints. The edge is not a bridge of : if it were, its endpoint subgraph would be a nontrivial block of met by , contrary to both endpoints surviving in . Consequently and are connected in ; otherwise adding to would merge their distinct components, so deleting would increase the component count. A path from to in , together with , forms a simple cycle with at least three vertices. This cycle is 2-connected, since deleting any vertex leaves a connected path. By [F1] it lies in a maximal 2-connected subgraph of . Therefore .
The edgeless case and the two possible types of cover all cases, so . No step used independence of .
Depends on
- Block containment and monotonicity under subgraphs
- Cutvertices, 2-connected pieces and nontrivial blocks
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
- 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
- A bridge as an edge whose deletion increases the number of connected components
- A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
- Cliques, independent sets, clique number and independence number
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.