skip to content

In a tree-shaped broadcast overlay, why does exactly one path connect any two nodes?

level: middleimportance: must knowfreq 50%

answer

  1. at least one, and at most one
  2. connectivity gives existence
  3. acyclicity gives uniqueness
  4. two paths diverge, then rejoin
  5. the rejoining stretch is a cycle

basics

~10 s

Because connectivity guarantees at least one path and acyclicity forbids a second: two distinct paths would diverge and rejoin, and that closed region is a cycle. Uniqueness is itself a definition of a tree.

solid answer

~50 s

A tree is **connected**, so at least one path joins any two nodes, and **acyclic**, so no more than one can. Suppose two different paths joined `u` and `v`. Follow them from `u`: they agree for a while, then diverge at some node, and since both end at `v` they must meet again later. The stretch between the divergence and the next meeting is a closed walk that repeats no link — a cycle. A tree has none, so the second path cannot exist. The converse holds too: if exactly one path joins every pair, the graph is connected by construction and acyclic, because any cycle would give the two paths around it between two of its own nodes. So "exactly one path between every pair" is not a consequence of tree-ness, it *is* one of the equivalent definitions.

go deeper

for a junior

Hold on to the statement itself: in a tree there is one route between any two nodes, never two and never none. That single fact explains why a message sent through it arrives once.

for a middle

Be able to run the argument both ways: connectivity gives existence, acyclicity gives uniqueness, and a second path would itself construct a cycle. Then state the converse that makes it a definition.

for a senior

Recognise the property behind the symptoms you operate: no duplicate delivery, no route choice, and a clean split into two parts when any one link is lost. Name the property rather than the symptom.

for a principal

Uniqueness is what you are actually buying or giving up when you choose a tree-shaped topology. Decide whether the absence of route choice is a simplification you want or a fragility you must offset.

## The property, stated precisely In an undirected graph, a **path** between nodes `u` and `v` is a sequence of distinct nodes starting at `u` and ending at `v` where each consecutive pair is joined by a link. The claim is that in a **tree** — a connected acyclic graph — there is exactly one such path for every choice of `u` and `v`, including when `u` and `v` are the same node, where the path is the trivial one with no links. The statement has two halves, and each comes from one of the tree's other two properties: - **At least one path** comes from connectivity. That is what connectivity means. - **At most one path** comes from acyclicity, and this is the half worth being able to argue. ## Why a second path forces a cycle Take two distinct paths `P` and `Q` from `u` to `v`. Walk both from `u` simultaneously. Because they are distinct, there is a first node `x` where they part company — up to `x` they used the same links, and at `x` they leave along different links. Because both eventually reach `v`, after `x` they must come together again; let `y` be the first node after `x` that lies on both. The stretch of `P` from `x` to `y` and the stretch of `Q` from `x` to `y` share only their two endpoints, and together they form a closed route that repeats no link: a **cycle**. A tree has no cycle, so `P` and `Q` cannot have been distinct. Note what the argument does *not* claim. It does not say the divergence node has three or more links: in a plain cycle, every node has exactly two links and yet two paths join every pair. Degree is not the mechanism; the absence of a closed route is. ## The converse, and why it makes this a definition Suppose a graph has exactly one path between every pair of nodes. Then it is connected, because "exactly one" implies "at least one". And it is acyclic, because if a cycle existed, any two distinct nodes on that cycle would be joined by two different paths — clockwise and anticlockwise around it. So uniqueness of paths implies connected and acyclic, and vice versa. That earns it a place in the list of equivalent characterizations, alongside "connected with exactly `n-1` links" and "acyclic with exactly `n-1` links". | Structure | Paths between a given pair | Broadcast consequence | |---|---|---| | Disconnected graph | zero for some pairs | some nodes never receive the message | | Tree | exactly one for every pair | every node receives it exactly once | | Connected graph with a cycle | at least two for some pairs | some nodes receive duplicates | ## What uniqueness buys Several everyday properties of tree-shaped overlays are really this one property wearing different clothes: - **A broadcast reaches each node exactly once.** A message flooded from any node travels the unique path to each other node, so no deduplication, no hop counter and no seen-set is needed to prevent repeats. - **Routing needs one link per node, not a table.** Because the route from any node towards a fixed root is unique, each node can store a single "next hop towards the root" and that is enough to reach it. Rooting a tree at any node turns unique paths into a parent pointer per node. - **Distance is well defined without a choice.** "The" distance between two nodes is the length of the only path, so there is no shortest-path question to resolve — a question that does arise the moment a second path exists. - **Every link is load-bearing.** Since the unique path between the two sides of a link is the link itself, losing it leaves those two sides with no path at all, and the overlay splits into exactly two pieces. ## The common way to get it wrong The phrase "there is a path between any two nodes" is about **connectivity** and is much weaker: a full mesh satisfies it and is nothing like a tree. The tree property is the word **exactly**. In an interview, the tell is a candidate who proves connectivity, declares the graph a tree and stops — the missing half is that no *second* route exists, which is the acyclicity half and the one with all the consequences.

  • Does the uniqueness argument need a node where three or more links meet?
    No, and assuming it does is a common slip. In a cycle every node has exactly two links, yet two distinct paths join every pair of nodes on it. What rules out a second path in a tree is the absence of any closed route, not a bound on how many links meet at a node.
  • How does unique-path-ness turn into a parent pointer per node?
    Pick any node as the root. For every other node, the unique path to the root has a well-defined first link, and the node at its far end is that node's parent. Because the path is unique, the parent is unambiguous, and following parents from anywhere terminates at the root without ever revisiting a node.

A road network where every town is reachable but no round trip exists: leaving any junction, there is never a choice of route to your destination, and every junction you leave behind is one you can never come back to.

saying these in an interview costs you the question

  • Confuses 'a path exists' with 'exactly one path exists'
  • Claims two distinct paths need a node of degree three
  • Thinks uniqueness follows from connectivity alone
  • Says a cycle gives only one path between its nodes
  • Assumes unique paths still hold once one link is added