LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 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.

Shortest-path distance is a metric on every connected component

Statement

Let $C$ be the vertex set of a connected component of a graph $G$ . The function $d_{G} : C \times C \to N$ satisfies, for all $u, v, w \in C$ ,

$d_{G} (u, v) \geq 0$ , with $d_{G} (u, v) = 0$ if and only if $u = v$ ;
$d_{G} (u, v) = d_{G} (v, u)$ ;
$d_{G} (u, w) \leq d_{G} (u, v) + d_{G} (v, w)$ .

These are the metric axioms, so shortest-path distance is a metric on $C$ .

Facts & Assumptions

Given: Vertices $u, v, w$ in one connected component $C$ of $G$ .

[F1]

$d_{G} (x, y)$ is the least length of an $x$ to $y$ path, and the length is a natural number (Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention).

[L1]

Every walk contains a path between the same endpoints whose length is no greater (Every walk between two vertices contains a path between the same endpoints).

[F2]

Reversing a path preserves its length, and concatenating an $x$ to $y$ path of length $a$ with a $y$ to $z$ path of length $b$ gives an $x$ to $z$ walk of length $a + b$ .

Proof

technique · direct

1.1

Every path length is a natural number, hence $d_{G} (u, v) \geq 0$ . The length- $0$ path $(u)$ gives $d_{G} (u, u) = 0$ . Conversely a path of length $0$ has one vertex, so $d_{G} (u, v) = 0$ forces $u = v$ .

1.2

Reversing a shortest $u$ to $v$ path gives a $v$ to $u$ path of the same length, so $d_{G} (v, u) \leq d_{G} (u, v)$ ; reversing the roles gives the opposite inequality, hence equality.

F1F2

1.3

Concatenate shortest paths from $u$ to $v$ and from $v$ to $w$ . This is a $u$ to $w$ walk of length $d_{G} (u, v) + d_{G} (v, w)$ , and [L1] supplies a $u$ to $w$ path of no greater length. Minimality in [F1] gives $d_{G} (u, w) \leq d_{G} (u, v) + d_{G} (v, w)$ .

F1F2L1

2.1

Steps 1.1, 1.2 and 1.3 establish separation, symmetry and the triangle inequality directly on $C$ , so $d_{G}$ is a metric there.

step 1.1step 1.2step 1.3∎

Depends on

Used by

On a finite vertex set the graph notions agree, and on connected graphs the two path distances agree Lemma

Dependency tree · two levels

5 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)