# Graph walks and simple paths

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

In a finite undirected simple graph, a walk requires each consecutive pair of vertices to be adjacent; a simple path additionally requires all vertices to be distinct.

mko-graph-walk-simple-path · definition · v0.10.0



## Mathematical statement

This slice fixes a finite undirected loop-free simple graph. A vertex sequence (v0,...,vk) is a walk if every consecutive unordered pair is an edge; its edge length is k. A simple path is a walk without repeated vertices. A walk may repeat vertices or edges; cycles and trails have additional obligations.





## Representative formula (exact TeX)

W(v)





## Assumptions


- Vertices are labeled 0 through n−1, with the complete undirected simple edge set and ordered vertex sequence explicit.
- An empty sequence is not a walk in this protocol; a singleton vertex is a length-zero simple path.





## Symbol scope


- G — finite undirected simple graph
- v — vertex sequence
- k — edge length





## Intuition, definition, and misconceptions

First check adjacency for each consecutive pair.

Length is the edge count: one less than the vertex-sequence length.

Simple paths forbid repeated vertices; general walks allow them.

An arbitrary vertex list need not be a walk; vertex count is not edge length, and a trail without repeated edges is not the same as a simple path.





## Adopted derivation guide

[Graph walks and simple paths: pair-by-pair checks, length and the difference from trails](https://ocme.evemisslab.com/en/derivations/derivation-mko-graph-walk-simple-path-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Finite simple undirected graphs](https://ocme.evemisslab.com/en/mko/mko-graph/) — The complete edge set specifies adjacency.
- [Sequence](https://ocme.evemisslab.com/en/mko/mko-sequence/) — A walk is represented by an ordered vertex sequence.
- [Binary relations and set projections](https://ocme.evemisslab.com/en/mko/mko-relation/) — Undirected adjacency is regarded as a symmetric relation.





## Verification boundary

Only the explicit finite undirected simple graph is handled; no general directed-walk, trail or cycle qualification is asserted.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add connected components.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/graph-walk-simple-path.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-graph-walk-simple-path/index.md)