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.
The connected components of a graph partition its vertex set and are its maximal connected subgraphs
Statement
The vertex sets of the connected components of a graph are nonempty, cover , and any two are equal or disjoint. Each induced graph is connected and contains every connected subgraph of that contains . Consequently the connected components are precisely the maximal connected subgraphs of .
Facts & Assumptions
Given: A graph and the reachability classes .
Reachability is an equivalence relation on (Being joined by a walk or path is the same equivalence relation on the vertex set).
is the set of vertices reachable from , and the connected component at is the induced graph (Connected graphs and connected components defined by the existence of vertex paths, Subgraphs, induced subgraphs and spanning subgraphs).
Proof
Reflexivity in [L1] gives , so every class is nonempty and the classes cover .
If and meet at , then reaches and reaches by symmetry; transitivity gives that reaches , and another use of symmetry and transitivity shows a vertex reaches exactly when it reaches . Thus , so distinct classes are disjoint.
If , then reaches and reaches ; concatenating these paths gives a walk from to , and deleting any repeated segments gives a path all of whose vertices remain reachable from . Hence is connected.
If a connected subgraph contains , every vertex of is joined to by a path in , hence also in , so . Thus is a subgraph of .
Steps 1.1 and 1.2 give the partition assertion, and steps 1.3 and 1.4 say exactly that its induced subgraphs are connected and maximal among connected subgraphs.
Depends on
Used by
- Every simple planar graph with n≥3 vertices has at most 3n-6 edges, with equality for every plane triangulation Corollary
- For a plane graph with c components, |V|-|E|+|F|=1+c, including the null graph Corollary
- A bridge as an edge whose deletion increases the number of connected components Definition
- A graph is P₃-free if and only if every connected component is complete Example
- Connected components, finite within-component distances, undefined cross-component distance and girth are computed in a disconnected graph Example
- A maximal acyclic spanning subgraph of a connected graph is a spanning tree Lemma
- Distinct connected components are anticomplete, and distinct anticonnected components are complete Lemma
- Every plane triangulation with at least three vertices is connected Lemma
- For every nontrivial connected graph, κ(G)≤λ(G) Lemma
- The anticonnected components of G are exactly the connected components of overline G Lemma
- A finite graph is bipartite if and only if it has no odd cycle Theorem
- An n-vertex simple graph with more than binomn-12 edges is connected Theorem
- Every graph with at least two vertices is connected or anticonnected Theorem
- For every forest, |V|=|E|+c, where c is the number of connected components Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 17 results over 12 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- R. Diestel, Graph Theory, Chapter 1 preview (standard reference, not scraped)