An overlay of n nodes reports exactly n-1 links: does that alone prove it reaches every node?

## The three properties For a finite undirected simple graph on `n` nodes, three properties can be checked independently: - **Connected** — every node is reachable from every other by some sequence of links. - **Acyclic** — no simple cycle: no closed walk that repeats no link and no node except its start. - **Exactly `n-1` links** — a pure count, with no reference to structure at all. A **tree** is a graph with all three. The theorem worth carrying is not "a tree has `n-1` links" but the stronger statement: **any two of the three properties imply the third**, and no one of them implies either of the others. ## Any two imply the third 1. **Connected + acyclic implies `n-1` links.** Build the graph up one node at a time. Start with a single node and no links. Every later node must arrive attached by at least one link (or it would be unreachable) and by at most one link into the part already built (a second link into the built part would close a cycle). So each of the `n-1` later nodes contributes exactly one link. 2. **Acyclic + `n-1` links implies connected.** An acyclic graph — a **forest** — with `n` nodes and `c` components has exactly `n-c` links, because each component is a tree on its own node set. Setting `n-c = n-1` gives `c = 1`. 3. **Connected + `n-1` links implies acyclic.** If a cycle existed, you could delete one of its links and stay connected, because the rest of that cycle still joins the two endpoints. That leaves a connected graph on `n` nodes with `n-2` links, which is impossible: a connected graph needs at least `n-1` links. ## Why the count alone proves nothing The counterexample is small enough to draw. Take six nodes. Wire `A-B`, `B-C`, `C-A` as a triangle, and `D-E`, `E-F` as a separate path. That is `3 + 2 = 5` links over `6` nodes, exactly `n-1` — and the graph is both cyclic and disconnected. The arithmetic explains itself: the triangle spends one link more than its three nodes need, and the shortfall reappears as a component that was never joined on. | What you observe | What you may conclude | What stays open | |---|---|---| | `n-1` links only | nothing structural | may be cyclic, may be split | | Connected only | at least `n-1` links | may carry extra links and cycles | | Acyclic only | at most `n-1` links | may be split into several pieces | | Connected + `n-1` links | it is a tree | — | | Acyclic + `n-1` links | it is a tree | — | ## Reading it off a running overlay The practical asymmetry is cost. Counting links is a scan of the membership table. Deciding connectivity or acyclicity means walking the graph — visiting nodes and links once each — which is the more expensive check but the one that carries information. That is why the count is best used as a **guard**: if a broadcast overlay over `n` nodes reports anything other than `n-1` links, it is certainly not a tree, and you stop there. If it reports exactly `n-1`, you still have to walk it once. Two bounds fall out of the same argument and are worth keeping separately: - **Any connected graph on `n` nodes has at least `n-1` links.** So `n-1` is the floor for reaching everyone, and a tree is a connected graph that sits exactly on the floor. - **Any connected graph on `n` nodes with `n` or more links contains a cycle.** So the moment an overlay carries one link beyond the floor, some redundancy exists — though not necessarily where you wanted it. ## Where this bites A broadcast overlay that is meant to be a tree but is quietly a forest-plus-cycle behaves in two bad ways at once: part of the cluster never receives the message, and another part receives it more than once around the loop. Both symptoms are consistent with the same innocent-looking link count, which is exactly why the count is not the check. State the pair you actually verified, and the third property is free.