Graph walks and simple paths

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

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 — The complete edge set specifies adjacency.
• Sequence — A walk is represented by an ordered vertex sequence.
• Binary relations and set projections — 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.