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.
Union closure for overlapping 2-connected subgraphs
Statement
If two 2-connected subgraphs and of a finite simple graph have at least two common vertices, their union is 2-connected.
Here the graph union is defined by , using binary set union for both coordinates.
Facts & Assumptions
A graph is 2-connected if it has at least three vertices, is connected, and remains connected after deletion of any one vertex. Cutvertices, 2-connected pieces and nontrivial blocks
A finite simple graph has a finite vertex set and edges that are two-element subsets of that set. A subgraph has a subset of the ambient vertex set and a subset of the ambient edges, with both endpoints of every edge in its vertex set. Every subset of a finite set is finite. A finite simple graph is a finite vertex set together with a set of two-element vertex subsets Subgraphs, induced subgraphs and spanning subgraphs A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
Binary set union is defined for any two sets; an element belongs to exactly when it belongs to or to . The union ⋃ x of a set, and the binary union a ∪ b := ⋃ {a,b} ⋃ ∅ = ∅, ⋃ {a} = a, ⋃ {a,b} = a ∪ b, ⋂ {a} = a, and ⋂ {a,b} = a ∩ b
A graph is connected when it is nonempty and every two vertices are joined by a path. A walk is a finite vertex list whose consecutive vertices are adjacent; a path has no repeated vertex, and a one-vertex list is a path of length zero. Every walk contains a path between its endpoints. 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 Every walk between two vertices contains a path between the same endpoints
Deleting a vertex removes that vertex and precisely the edges incident with it, leaving the induced subgraph on the remaining vertices. Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
Proof
Given: The graphs and overlap hypothesis in the Statement.
Goal: The graph union defined there is 2-connected.
Write for the finite simple ambient graph and for the graph specified in the Statement. Every vertex of lies in , so its vertex set is finite. Each edge of is an edge of or , hence is an edge of with two distinct endpoints in . Thus is a finite simple subgraph of containing both and . In particular, it has at least three vertices.
Choose a common vertex of and . For arbitrary , choose one of containing and one containing . Both chosen subgraphs also contain and are connected, so they supply a path from to and a path from to . Concatenate their vertex lists, listing the joint vertex only once. Consecutive vertices are adjacent in , so the result is a walk, even if other vertices repeat. The walk-to-path result yields a path from to in . Therefore is connected.
Fix any . For or , let if , and let otherwise. The vertices of are exactly the vertices of other than . An edge belongs to exactly when it belongs to at least one of and is not incident with ; these are exactly the edges of . Hence .
Each of is connected: when belongs to the original subgraph this follows from 2-connectivity, and otherwise that connected subgraph is unchanged. Of the at least two common vertices of and , at least one is different from and remains in both and . The path-concatenation and walk-to-path argument of step 2.1, through this surviving common vertex, therefore connects every pair of vertices of . By step 2.2 this says that is connected. Since was arbitrary and is connected with at least three vertices, is 2-connected.
Depends on
- Cutvertices, 2-connected pieces and nontrivial blocks
- Subgraphs, induced subgraphs and spanning subgraphs
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- The union ⋃ x of a set, and the binary union a ∪ b := ⋃ {a,b}
- ⋃ ∅ = ∅, ⋃ {a} = a, ⋃ {a,b} = a ∪ b, ⋂ {a} = a, and ⋂ {a,b} = a ∩ b
- A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
- 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
- Every walk between two vertices contains a path between the same endpoints
- 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.