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.
Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
Definition
Let be a graph. A walk of length is a finite vertex list
such that for every . Its endpoints are and . The length is the number of traversed edges, not the number of displayed vertices. A walk is closed when .
A trail is a walk in which the traversed edges are distinct. A path is a walk in which the vertices are distinct. In particular, is a path of length from to itself.
A cycle is a closed walk of length in which are distinct. A graph is acyclic when it contains no cycle. Reversing any walk, trail, path, or cycle preserves its type and length.
Depends on
Used by
- Every finite simple graph of minimum degree at least two contains a cycle Corollary
- Every tree with at least two vertices has at least two leaves Corollary
- Every triangle-free simple planar graph with n≥3 vertices has at most 2n-4 edges Corollary
- Alternating and augmenting paths relative to a matching Definition
- Arc-disjoint, edge-disjoint and internally vertex-disjoint path families and their local separators Definition
- Connected graphs and connected components defined by the existence of vertex paths Definition
- Directed walks, trails, paths and cycles, and strong connectivity Definition
- Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices Definition
- Euler trails and Euler circuits in multigraphs and digraphs Definition
- Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention Definition
- Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs Definition
- Trees, forests, leaves and isolated vertices Definition
- A small graph separates walks, trails, paths, closed walks and cycles by explicit vertex lists Example
- Adding an edge between two nonadjacent vertices of a tree creates exactly one cycle Lemma
- An edge of a finite graph is a bridge if and only if it lies on no cycle Lemma
- Being joined by a walk or path is the same equivalence relation on the vertex set Lemma
- Deleting any edge of a tree separates it into exactly two tree components Lemma
- Every closed walk of odd length contains a cycle of odd length Lemma
- Every walk between two vertices contains a path between the same endpoints Lemma
- For five cyclically ordered neighbours of a plane vertex, alternating Kempe paths between the first and third and between the second and fourth cannot both occur Lemma
- If two distinct faces of a connected plane graph have the same boundary subgraph, then the graph is a cycle Lemma
- The symmetric difference of two matchings is a disjoint union of alternating paths and even cycles Lemma
- A two-connected plane graph of order at least three is maximal exactly when every face is triangular Proposition
- Every face of a two-connected plane graph is bounded by a cycle Proposition
- Equivalent characterisations of a nonempty tree by unique paths, edge count, minimal connectivity and maximal acyclicity Theorem
- Every nonempty finite simple graph contains a path with at least δ(G) edges Theorem
- The Ramsey number R(3,3)=6 Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 10 results over 8 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
- University of Lethbridge, Combinatorics: A Guided Tour, Paths and Cycles (standard reference, not scraped)