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.
A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
Definition
A finite simple graph is an ordered pair in which is a finite set and
The elements of are the vertices and the elements of are the edges. Thus every edge has two distinct endpoints, there are no loops, and an unordered pair of vertices occurs as at most one edge. Finiteness and the notation and are those of The cardinality of a finite set.
When no qualifier is present, the word graph has this meaning.
Depends on
Used by
- There are 2^binomn2 simple graphs on a fixed labelled n-element vertex set Corollary
- A bipartite graph and a proper two-colouring of its vertices Definition
- Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree Definition
- Cliques, independent sets, clique number and independence number Definition
- Cliques, stable sets, the clique number ω(G) and stability number α(G) Definition
- Degree in a multigraph, indegree and outdegree in a digraph, and their underlying connectivity Definition
- Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs Definition
- Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices Definition
- Graph isomorphisms, automorphisms and graph complements Definition
- Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs Definition
- Induced embeddings and induced copies of a graph Definition
- Matchings, saturated vertices, maximal and maximum matchings, perfect matchings and ν(G) Definition
- Multigraphs, loops and directed graphs as variants distinct from the default finite simple graph Definition
- Plane embeddings of finite simple graphs, their faces, facial boundary walks and lengths (counting a bridge twice), and planar graphs Definition
- Proper vertex colourings and chromatic number Definition
- Subgraphs, induced subgraphs and spanning subgraphs Definition
- The Bondy-Chvatal closure of a finite simple graph Definition
- The line graph whose vertices are the edges of the original graph and whose adjacency records a shared endpoint Definition
- The Petersen graph on the two-element subsets of a five-element set, adjacent when disjoint Definition
- Trees, forests, leaves and isolated vertices Definition
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors Definition
- Vertex covers, edge covers and the covering numbers τ(G) and ρ(G) Definition
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges Definition
- A small graph separates walks, trails, paths, closed walks and cycles by explicit vertex lists Example
- The set of spanning trees of a finite graph is finite Lemma
- Unless stated otherwise, graph means finite, simple and undirected; orders, sizes and empty-set conventions are fixed here Remark
- An n-vertex simple graph with more than binomn-12 edges is connected Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 24 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)