DefinitionDefinition: AI-adaptedProof: Not applicableSession-authored (Fable 5 assisted)audited 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 $\varnothing$ 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\ge1$ , take vertices $0,\ldots,n-1$ and edges $\{i,i+1\}$ for $0\le 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\ge3$ : it has vertices $0,\ldots,n-1$ , the consecutive edges $\{i,i+1\}$ for $0\le 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 nonempty hereditary graph class contains the null graph Corollary
K₅ and K_3,3 are nonplanar Corollary
The complete graph on an n-element vertex set has binomn2 edges Corollary
A graph on n vertices with n-1 edges need not be a tree 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
C₆ and the disjoint union of two triangles have the same degree sequence but are not isomorphic 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
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 middle edge of P₄ is a maximal matching but the two end edges form a larger matching 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 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 tournament is an orientation of a complete finite graph Definition
Cliques, stable sets, the clique number ω(G) and stability number α(G) Definition
Maximal plane graphs, plane triangulations, and maximally planar abstract graphs Definition
Vertex cuts, edge cuts, vertex connectivity κ(G) and edge connectivity λ(G), with conventions for complete and one-vertex graphs Definition
A connected graph with two distinct spanning trees Example
A graph is P₃-free if and only if every connected component is complete Example
Complete graphs form the hereditary class with forbidden basis {overline K₂} Example
Complete, anticomplete and mixed vertex-set pairs in P₄ Example
Edgeless graphs form the hereditary class with forbidden basis {K₂} Example
Euler's formula checked on a plane tree, a cycle, and the four-face embedding of K₄ Example
In K_2,3, the two vertices in the two-part have three internally disjoint paths and a minimum separator of size three Example
K_3,3 has a Hamilton cycle Example
K₄ with one new vertex adjacent to two clique vertices satisfies Ore's condition but not Dirac's condition Example
K₅ and K_3,3 illustrate complete and complete bipartite graphs, degrees and edge counts Example
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 complete graph Kₙ has chromatic number n Example
The isomorphism types of trees on at most five vertices Example
τ(Cₙ)=n for every n≥3 Example
Every hereditary graph class has a finite forbidden induced-subgraph basis False statement

…and 7 more results.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 13 results over 9 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)

Empty and complete graphs, complete bipartite graphs, and the convention that PnP_nPn​ and CnC_nCn​ have nnn vertices