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.
Nonempty remainder after deleting an independent set
Statement
If a finite simple graph has an edge and is independent, then is nonempty. Its induced graph is finite. If this remainder has an edge, its maximum nontrivial block order is at least two.
An independent set contains no edge with both endpoints in it. The induced graph on , also written , has that vertex set and precisely the edges of with both endpoints in it. A nontrivial block is either a maximal 2-connected subgraph or a bridge together with its two endpoints; 2-connected graphs have at least three vertices. The order of a graph is its number of vertices.
Facts & Assumptions
Every edge of a simple graph has two distinct endpoints. An independent set contains no edge with both endpoints in it. A finite simple graph is a finite vertex set together with a set of two-element vertex subsets Cliques, independent sets, clique number and independence number
A subset of a finite set is finite. Vertex deletion produces the induced graph on the remaining vertices, whose edges are those of the original graph with both endpoints remaining. A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors Subgraphs, induced subgraphs and spanning subgraphs
A nonempty finite graph with an edge has at least one nontrivial block, and its maximum block order exists. Each nontrivial block is either 2-connected with at least three vertices or a bridge-edge subgraph with two vertices. Graph order is the finite cardinality of the vertex set. Cutvertices, 2-connected pieces and nontrivial blocks The cardinality | A| of a finite set
Proof
Given: A finite simple graph with an edge and an independent set .
Goal: Prove that is nonempty and finite, and that its maximum nontrivial block order is at least two if it has an edge.
Choose an edge of . Its endpoints are distinct and cannot both belong to , so at least one belongs to . This set is a subset of the finite set and is therefore finite. Consequently , the induced graph on it, is a nonempty finite simple graph.
If has an edge, its nontrivial block family is nonempty and has a maximum order. Every member has at least two vertices, whether it is 2-connected or a bridge-edge subgraph. Therefore the maximum order is at least two. This proves all the assertions.
Depends on
- Cliques, independent sets, clique number and independence number
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Subgraphs, induced subgraphs and spanning subgraphs
- The cardinality | A| of a finite set
- A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
- Cutvertices, 2-connected pieces and nontrivial blocks
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.