Why does 'reachable from' split an undirected backbone into components with every site in exactly one?

## The relation being claimed Take the backbone as an undirected graph — sites as vertices, spans as edges — and define one relation on the sites: `u ~ v` holds when **some walk of spans runs from `u` to `v`**. A walk is any sequence of sites with a span between each consecutive pair; it is allowed to repeat sites and spans. The claim is that this relation is an **equivalence relation**, and that is the whole reason "connected component" is a well-defined idea rather than a loose word for "a blob of the diagram". ## The three checks 1. **Reflexive.** `u ~ u` for every site, using the walk of length zero that starts and stops at `u`. This is not a technicality: it is what puts a site with no spans at all into a component of its own rather than into none. 2. **Symmetric.** If a walk runs from `u` to `v`, reversing the sequence gives a walk from `v` to `u`, because an undirected span may be traversed either way. This is the step that depends on the graph being undirected. 3. **Transitive.** If a walk runs `u` to `v` and another runs `v` to `w`, concatenating them at `v` gives a walk from `u` to `w`. Concatenation is safe precisely because a **walk** is permitted to repeat sites and spans — the join may well revisit `v`. ## Walks are enough, because every walk contains a path Defining the relation with walks rather than paths is deliberate, and it costs nothing. If a walk from `u` to `v` visits some site twice, delete everything between the two visits; the result is still a walk from `u` to `v`, and it is strictly shorter. Repeat until no site occurs twice, and what remains is a **path**. So "there is a walk" and "there is a path" are the same statement about reachability, but the walk version makes transitivity a one-line argument instead of a case analysis. | relation property | what it is in the graph | what breaks without it | |---|---|---| | reflexive | a site reaches itself by the empty walk | a site with no spans would belong to no component | | symmetric | an undirected span traverses either way | two classes could overlap without being equal | | transitive | two walks join end to end into one walk | a class could contain a pair that cannot reach each other | ## Why the classes partition the sites An equivalence relation's classes are its blocks: the class of `u` is the set of sites related to `u`. Two facts give the partition. - **Every site is in a class** — its own, by reflexivity. Nothing is left over. - **Two classes that meet are identical.** Suppose site `w` lies in the class of `u` and in the class of `v`. Then `u ~ w` and `v ~ w`; symmetry turns the second into `w ~ v`, and transitivity gives `u ~ v`, so anything related to one is related to the other and the two classes coincide. No site is left out and no site is in two classes, which is exactly what "partition" means. The classes are the **connected components**, and the number of classes is the number of pieces the network is in. ## What this buys an operator The payoff is that every statement about a partitioned network becomes unambiguous: - "the backbone is in three pieces" has a definite meaning, and each site is in precisely one of them; - a site's component is a property of the site, not of the route you happened to trace or of where you started looking; - adding one span either joins two components into one or leaves the count unchanged — it can never raise it, and it can never merge three at once; - removing a span or a site can raise the count, and the failures that do so are exactly the bridges and cut vertices an audit hunts for. The last two points also give a cheap sanity check on any reported fault: if a single span cut is claimed to have produced three pieces from one, the report is wrong about something, because one edge removal can add at most one component. ## The one assumption that does the work Everything above rests on symmetry, and symmetry rests on the spans being undirected. If the spans were one-way, "reachable from" would no longer be symmetric — `u` could reach `v` with no route back — and the classes-partition argument fails at its second step. Directed networks therefore need a different relation, built on **mutual** reachability, which is a subject of its own. On an undirected backbone the simple relation is enough, and that is why the component count is such a blunt, reliable way to describe damage.