Connected component

Mathematical statement

In a finite undirected loop-free simple graph, u and v are connected if a path joins them; length-zero paths ensure reflexivity. The equivalence classes are the maximal connected components, mutually disjoint and covering every vertex. Isolated vertices form singleton components.

Representative formula (exact TeX)

Q(G)

Assumptions

• Vertex labels 0 through n−1 and the complete undirected simple edge set are explicit.
• Reachability is checked by complete BFS or DFS, not switched to directed weak or strong connectivity.

Symbol scope

• Q — connected-component partition
• G — finite undirected simple graph

Intuition, definition, and misconceptions

Every vertex is connected to itself by a length-zero path.

Complete BFS or DFS from a start vertex finds its exact component.

Components are disjoint and cover all vertices; isolated vertices must not be omitted.

Ignoring isolated vertices, treating one visit order as a component certificate, or mixing directed strong and weak connectivity is invalid.

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

• Graph walks and simple paths — Connectivity is defined by the existence of a path.
• Equivalence relation — Reachability in an undirected graph forms an equivalence relation.
• Finite simple undirected graphs — The complete vertex and edge sets supply the search space.

Verification boundary

Only complete finite undirected simple graphs are handled; directed, infinite and dynamic graphs are not inferred.

not_formalized

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

Next obligation

Add component contraction and graph-algorithm complexity.

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.