# Connected component

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, connected components are exactly the vertex equivalence classes defined by the existence of a path.

mko-connected-component · definition · v0.10.0



## 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

[Connected components: finding every component of a finite simple graph by complete BFS](https://ocme.evemisslab.com/en/derivations/derivation-mko-connected-component-01/)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](https://ocme.evemisslab.com/en/mko/mko-graph-walk-simple-path/) — Connectivity is defined by the existence of a path.
- [Equivalence relation](https://ocme.evemisslab.com/en/mko/mko-equivalence-relation/) — Reachability in an undirected graph forms an equivalence relation.
- [Finite simple undirected graphs](https://ocme.evemisslab.com/en/mko/mko-graph/) — 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.

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