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.
Anticonnected graphs and anticonnected components
Definition
A graph is anticonnected, or co-connected, when its complement is connected (Connected graphs and connected components defined by the existence of vertex paths, Graph isomorphisms, automorphisms and graph complements).
An anticonnected component, or anticomponent, of is a vertex set that is the vertex set of a connected component of . Equivalently, is anticonnected and is inclusion-maximal with that property (Subgraphs, induced subgraphs and spanning subgraphs).
Under the library convention, the null graph is not anticonnected, while a one-vertex graph is anticonnected.
Depends on
Used by
- The prime quotient produced by the modular decomposition of a connected and anticonnected graph has at least four vertices Corollary
- Maximal proper modules need not be disjoint when the graph or its complement is disconnected Counterexample
- Wonderful finite graph families Definition
- P₄ is both connected and anticonnected Example
- Substituting into K₂ gives the join and substituting into K₂ gives the disjoint union Example
- Two large anticonnected components give a complete two-blockade Example
- Up to isomorphism the four-vertex path is the only prime graph on four vertices Example
- A complete-or-weakly-sparse blockade yields a complete subblockade or an anticonnected thinning Lemma
- A hatted-five-cycle-free rooted stable-tooth comb yields a large pure blockade of components Lemma
- A quotient block of connected or anticonnected blocks is again connected or anticonnected Lemma
- A semisparse blockade can be sampled to anticonnected blocks with nearly pure relations Lemma
- A vertex mixed on an anticonnected set yields opposite adjacency on a nonedge Lemma
- A wonderful anticonnected complete-or-sparse blockade yields a restricted subgraph or a large anticomplete pair Lemma
- Anticonnected block contraction turns an upside-down comb into a pure blockade Lemma
- E overlap classes form an anticonnected partition Lemma
- Every union of connected components is a module, and so is every union of anticonnected components Lemma
- In a connected and anticonnected graph, the union of two proper modules that meet is again a proper module Lemma
- Mixed anticonnected blocks lift pattern obstructions to the ambient graph Lemma
- Small anticonnected components yield a complete blockade Lemma
- The anticonnected components of G are exactly the connected components of Ḡ Lemma
- Every graph with at least two vertices is connected or anticonnected Theorem
- Every nontrivial cograph is disconnected or has disconnected complement Theorem
- Every nontrivial P₄-free graph is disconnected or has disconnected complement Theorem
- Gallai's modular decomposition theorem: a graph on at least two vertices is disconnected, or has a disconnected complement, or has a modular partition into its maximal proper modules whose quotient is prime Theorem
- The cographs are exactly the P₄-free graphs Theorem
Dependency tree · two levels
8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Valerio Boncompagni, On hereditary graph classes defined by forbidding Truemper configurations (PhD thesis, 2018) (standard reference, not scraped)