DefinitionDefinition: AI-adaptedProof: Not applicableaudited 2026-07-31

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.

Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices

Definition

On a finite vertex set $V$ , the empty graph has edge set $\emptyset$ and the complete graph $K_{V}$ has edge set $[V]^{2}$ . When $V$ is an $n$ -element labelled set, these are also denoted ${\overline{K}}_{n}$ and $K_{n}$ .

For disjoint finite sets $A$ and $B$ , the complete bipartite graph $K_{A, B}$ has vertex set $A \cup B$ and edge set

${{a, b} : a \in A, b \in B} .$

If $∣ A ∣ = m$ and $∣ B ∣ = n$ , it is denoted $K_{m, n}$ .

The path graph $P_{n}$ has $n$ vertices. For $n \geq 1$ , take vertices $0, \dots, n - 1$ and edges ${i, i + 1}$ for $0 \leq i < n - 1$ ; it has length $n - 1$ . Set $P_{0}$ equal to the null graph. The cycle graph $C_{n}$ is defined only for $n \geq 3$ : it has vertices $0, \dots, n - 1$ , the consecutive edges ${i, i + 1}$ for $0 \leq i < n - 1$ , and the closing edge ${n - 1, 0}$ . Thus in this notation the subscript records the number of vertices, not the length of a path.

Depends on

Used by

Every bipartite graph with at least one edge has Turán density zero Corollary
Every graph on at most three vertices has the Erdős–Hajnal property Corollary
Every nonempty hereditary graph class contains the null graph Corollary
K₅ and K_3,3 are nonplanar Corollary
Substituting a complete or an edgeless graph for a vertex preserves the Erdős–Hajnal property Corollary
The complete graph on an n-element vertex set has C(n, 2) edges Corollary
The five-cycle has the Erdős-Hajnal property Corollary
The five-vertex path and its complement have the Erdős-Hajnal property Corollary
The four-vertex path has the Erdős-Hajnal property Corollary
The star-expansion of the four-vertex path and its complement have the Erdős-Hajnal property Corollary
A difference of two nested modules that is not a module Counterexample
A graph on n vertices with n-1 edges need not be a tree Counterexample
A star has tiny self-density, yet no restricted subset containing its centre has more than two vertices Counterexample
A vertex order on P₄ makes greedy colouring use three colours although χ(P₄)=2 Counterexample
A weighted graph with two distinct minimum spanning trees Counterexample
An acyclic graph need not be a tree Counterexample
An induced subgraph of a prime graph need not be prime Counterexample
C₆ and the disjoint union of two triangles have the same degree sequence but are not isomorphic Counterexample
Induced removal must permit adding edges as well as deleting them Counterexample
K_3,3 satisfies |E|≤3|V|-6 but is nonplanar, so the planar edge bound is not sufficient Counterexample
K₃ contains P₃ as a subgraph but not as an induced subgraph Counterexample
K₃ has ν(K₃)=1<2=τ(K₃), so König's equality needs bipartiteness Counterexample
K₄ is Hamiltonian but has no Euler circuit Counterexample
K₄ is planar but has chromatic number four, so the five-colour bound cannot be lowered to three Counterexample
Maximal proper modules need not be disjoint when the graph or its complement is disconnected Counterexample
P₃ has a Hamilton path but no Hamilton cycle Counterexample
The class of connected graphs is not hereditary Counterexample
The class of regular graphs is not hereditary Counterexample
The dense alternative in Rödl's theorem cannot be dropped Counterexample
The five-cycle is bull-free but not perfect Counterexample
The half graph has no regularity across its natural bipartition at a fixed small parameter Counterexample
The middle edge of P₄ is a maximal matching but the two end edges form a larger matching Counterexample
The polynomial Rödl witness need not be the whole graph Counterexample
Two cospectral graphs need not be isomorphic Counterexample
Two disjoint copies of Kₘ show that Dirac's bound cannot be lowered to n/2-1 for even n=2m≥4 Counterexample
Two disjoint modules whose union is not a module Counterexample
Two triangles sharing one vertex form a connected simple graph with all degrees even that is not a cycle Counterexample
Two triangles sharing one vertex form an Eulerian graph with no Hamilton cycle Counterexample
A decomposition of a graph's edge set into complete bipartite subgraphs Definition
A tournament is an orientation of a complete finite graph Definition

…and 106 more results.

Dependency tree · two levels

6 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

R. Diestel, Graph Theory, Chapter 1 preview (standard reference, not scraped)

Empty and complete graphs, complete bipartite graphs, and the convention that PnPn​ and CnCn​ have nn vertices