Why does adding one extra link to a tree-shaped overlay create exactly one cycle?

## The claim and the two halves of its argument Start with a tree `T` on `n` nodes and `n-1` links, and add one link `uv` between two nodes that are not already joined by a link. The result `T + uv` has `n` links, and the claim is that it contains **exactly one cycle**. Like most "exactly" claims, the argument has a lower half and an upper half: 1. **At least one cycle exists.** `T` is connected, so `u` and `v` are joined by a path `P`. Appending `uv` to `P` gives a closed route that repeats no link and no node other than its start: a cycle. 2. **At most one cycle exists.** Any cycle in `T + uv` must use the link `uv`, since removing `uv` leaves `T`, which is acyclic. A cycle through `uv` is exactly `uv` plus a path from `u` to `v` that avoids `uv` — that is, a path inside `T`. A tree has exactly one such path, so there is exactly one such cycle. The cycle produced this way is called the **fundamental cycle** of `uv` with respect to `T`. Its length is one more than the number of links on the tree path between `u` and `v`, which is why a link added between two nearby nodes creates a short loop and one added between two far-apart nodes creates a long one. ## The characterization it belongs to This is the mirror image of another tree property, and the pair is worth stating together: | Direction | Statement | What the tree sits on | |---|---|---| | Remove a link | The graph splits into exactly two parts | minimally connected | | Add a link | Exactly one cycle appears | maximally acyclic | A tree is exactly the boundary between the two regimes: it has no slack to lose and no room to gain. Either of these statements, taken with connectivity or acyclicity respectively, is a valid definition of a tree — they sit beside "connected and acyclic", "connected with `n-1` links" and "exactly one path between every pair". ## Adding more than one link The "exactly one" figure does not simply multiply. Two quantities are easy to confuse: - **Independent cycles** — the dimension of the graph's cycle space — is `E - V + 1` for a connected graph, so a tree plus `k` extra links has exactly `k` independent cycles, one fundamental cycle per added link. - **Distinct cycles** — how many closed routes you could actually trace — can be larger. With two added links whose fundamental cycles share at least one link, the two cycles combine into a third: drop the shared links and the outer boundary is a cycle of its own. So two added links give **two** distinct cycles when their fundamental cycles are link-disjoint, and **three** when they overlap. With `k` added links the distinct-cycle count sits between `k` and `2^k - 1`, which is why "one link, one cycle" is a statement about the first link and not a rate. ## Why an overlay designer cares Take a broadcast overlay wired as a tree over a cluster. A message flooded from any node reaches every other node exactly once, because the route to each is unique. Now add one link, for whatever reason — a helpful shortcut, an operator repairing something, two nodes discovering each other: - A message entering the fundamental cycle travels both ways around it, so every node on that cycle receives it **twice**, and the flood no longer terminates on structure alone. - The overlay therefore needs a termination rule it did not need before: a seen-set, a message identifier, or a hop limit. That cost appears at the first extra link, not gradually. - The nodes *outside* the cycle are unaffected in delivery count — they still sit on a tree hanging off it. The duplication is local to the loop, which is why the length of the fundamental cycle, not just its existence, tells you how much of the cluster is affected. ## The traps The first trap is symmetry: people say "two cycles, one in each direction". Direction is not a property of a cycle in an undirected graph; clockwise and anticlockwise trace the same link set and are the same cycle. The second is assuming the added link must join two distant nodes to matter — a link between two nodes that are already neighbours-of-a-neighbour creates a three-link cycle, which is still a cycle and still duplicates. The third is extrapolating the count, which the section above corrects.