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.
The path metric of a connected simple graph
Definition
Let be a connected simple graph. For vertices , connectedness supplies at least one path from to , and every such path has a length in . By The well-ordering principle, the set of these lengths has a least element. The path metric of is therefore the function
Here is the number of edges traversed by the path , as in Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges. The proof that is a metric in the sense of Metric space: iff , symmetry, and the triangle inequality; pseudometric and ultrametric is The path metric of a connected simple graph is a metric on its vertex set.
Depends on
- Simple graphs on an arbitrary vertex set
- Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set
- Every walk contains a path between the same endpoints, of no greater length
- Metric space: $d(x,y) = 0$ iff $x = y$, symmetry, and the triangle inequality; pseudometric and ultrametric
- The well-ordering principle
Used by
- A bijection of vertex sets is an isometry for the path metrics if and only if it is a graph isomorphism Lemma
- For a finite group the Cayley graph is a finite simple graph in the published sense and the two distances agree 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
- The vertex set of a connected simple graph with its path metric is a (1,1)-quasi-geodesic space Proposition
- The path metric of a connected simple graph is a metric on its vertex set Theorem
- The word metric is a left-invariant metric and coincides with the path metric of the Cayley graph Theorem
Dependency tree · two levels
23 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 5.2 (standard reference, not scraped)