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.
Graph isomorphisms, automorphisms and graph complements
Definition
Let and be graphs. A graph isomorphism is a bijection (Injection, surjection, bijection) such that, for all distinct ,
Graphs are isomorphic, written , when such a map exists. An automorphism of is an isomorphism from to itself.
The complement of is the graph
Thus exactly one of and contains any given pair of distinct vertices as an edge, and .
Depends on
Used by
- G is H-free if and only if overline G is overline H-free Corollary
- C₆ and the disjoint union of two triangles have the same degree sequence but are not isomorphic Counterexample
- Anticonnected graphs and anticonnected components Definition
- Hereditary graph classes Definition
- Induced embeddings and induced copies of a graph Definition
- The complement of a graph class Definition
- P₄ is both connected and anticonnected Example
- R(3,3)=6 in both directions: the six-vertex argument and the red 5-cycle whose blue complement is another 5-cycle Example
- The isomorphism types of trees on at most five vertices Example
- FALSE: a finite simple graph is determined up to isomorphism by its degree sequence False statement
- Complementation swaps cliques with stable sets, so ω(overline G)=α(G) Lemma
- ind_H(G) is isomorphism-invariant and equals ind_overline H(overline G) Lemma
- Induced embeddings compose, and the induced-subgraph relation is transitive up to isomorphism Lemma
- overlineG[W]=overline G[W] for every vertex set W Lemma
- Purity is symmetric; complementation swaps complete and anticomplete pairs and preserves mixed pairs Lemma
- Every connected plane graph has a plane dual multigraph, and when that dual is simple the reciprocal embedding identifies the double dual with the original graph Theorem
- Every graph with at least two vertices is connected or anticonnected Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 18 results over 11 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)