ExampleConstruction: AI-generatedVerification: 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.

Connected components, finite within-component distances, undefined cross-component distance and girth are computed in a disconnected graph

Example

Let $G$ have vertices $a, b, c, p, q, r$ and edges $a b, b c, c a, p q, q r$ . Its components are the triangle on ${a, b, c}$ and the path on ${p, q, r}$ . Within them,

$d (a, b) = 1, d (p, q) = 1, d (p, r) = 2.$

The distance $d (a, p)$ is undefined. The graph has girth $3$ ; its path component is acyclic and has girth $\infty$ .

Facts & Assumptions

Given: The graph $G$ described in the Example.

[F1]

Components are induced by path-reachability, and the component vertex sets partition the graph (Connected graphs and connected components defined by the existence of vertex paths, The connected components of a graph partition its vertex set and are its maximal connected subgraphs).

[F2]

Distance is the minimum path length within one component and is not assigned across components; girth is the least cycle length, with value $\infty$ for an acyclic graph (Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention).

Verification

technique · direct

1.1

The vertices $a, b, c$ reach one another along triangle edges, and $p, q, r$ reach one another along $p q, q r$ . No edge joins these two sets, so [F1] gives exactly the two stated components.

givenF1

1.2

The edges $a b$ and $p q$ give the two distances $1$ . The path $(p, q, r)$ has length $2$ , while $p$ and $r$ are not adjacent, so $d (p, r) = 2$ .

givenF2

2.1

Since $a$ and $p$ lie in different components, $d (a, p)$ is undefined by [F2]. The triangle is a cycle of length $3$ , no cycle can have smaller length, and the path component has no cycle; the girth assertions follow.

step 1.1F2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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

University of Lethbridge, Combinatorics: A Guided Tour, Paths and Cycles (standard reference, not scraped)