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.
Subgraphs, induced subgraphs and spanning subgraphs
Definition
Let be a graph. A graph is a subgraph of when and .
For , the subgraph induced by is
Thus it retains every edge of whose two endpoints lie in . A subgraph is induced when , and it is spanning when . These constructions remain finite simple graphs by A finite simple graph is a finite vertex set together with a set of two-element vertex subsets.
Depends on
Used by
- Every nonempty hereditary graph class contains the null graph Corollary
- The connected components of a graph partition its vertex set and are its maximal connected subgraphs Corollary
- K₃ contains P₃ as a subgraph but not as an induced subgraph Counterexample
- The class of connected graphs is not hereditary Counterexample
- The class of regular graphs is not hereditary Counterexample
- Anticonnected graphs and anticonnected components Definition
- Cliques, stable sets, the clique number ω(G) and stability number α(G) Definition
- Connected graphs and connected components defined by the existence of vertex paths Definition
- Induced embeddings and induced copies of a graph Definition
- Kempe chains as connected components induced by two colour classes Definition
- Minimal forbidden induced subgraphs and forbidden bases Definition
- Plane embeddings of finite simple graphs, their faces, facial boundary walks and lengths (counting a bridge twice), and planar graphs Definition
- Spanning trees of a graph Definition
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors Definition
- A worked graph records vertex deletion, edge deletion, edge contraction and the resulting minor model Example
- Adding an edge between two nonadjacent vertices of a tree creates exactly one cycle Lemma
- Every face of a plane subgraph contains each face of the original graph that it meets Lemma
- Hall's condition passes to the strict and tight induction subinstances Lemma
- In an edge-maximal graph with no K₅ or K_3,3 subdivision, a minimum proper separation of order at most two has an adjacent two-vertex separator and edge-maximal sides Lemma
- overlineG[W]=overline G[W] for every vertex set W Lemma
- The symmetric difference of two matchings is a disjoint union of alternating paths and even cycles Lemma
- In a three-connected plane graph, face boundaries are exactly the induced cycles whose deletion leaves the graph connected Proposition
- Equivalent characterisations of a nonempty tree by unique paths, edge count, minimal connectivity and maximal acyclicity Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 9 results over 7 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)