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.
Simple graphs on an arbitrary vertex set
Definition
A simple graph is an ordered pair in which is a set and
The elements of are the vertices and the elements of are the edges. Thus a simple graph has no loops and no parallel edges.
This is the same incidence convention as A finite simple graph is a finite vertex set together with a set of two-element vertex subsets, with the word "finite" removed from the hypothesis on . Whenever a statement on this page is made for a simple graph, it allows an arbitrary vertex set unless finiteness is stated separately.
Depends on
Used by
- Cycles, trees and forests in a simple graph on an arbitrary vertex set Definition
- Labelled directed graphs, their underlying simple graphs, and label-preserving isomorphisms Definition
- Locally finite graphs and vertex degree without a finiteness hypothesis Definition
- The Cayley graph of a group with respect to a subset Definition
- The path metric of a connected simple graph Definition
- Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set Definition
- A bijection of vertex sets is an isometry for the path metrics if and only if it is a graph isomorphism Lemma
- Every walk contains a path between the same endpoints, of no greater length Lemma
- In a connected locally finite graph every ball of the path metric is finite Lemma
- On a finite vertex set the graph notions agree, and on connected graphs the two path distances agree Lemma
- A nonempty simple graph is a tree if and only if each pair of vertices is joined by exactly one path Theorem
- The path metric of a connected simple graph is a metric on its vertex set Theorem
Dependency tree · two levels
3 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
- C. Loh, Geometric Group Theory: An Introduction (2015 course version), Section 3.1 (standard reference, not scraped)