In a mesh of n machines with no self-links or duplicate links, what is the maximum possible number of links?
answer
- a link is an unordered pair
- every pair joined at most once
- each machine tops out one below n
- halve, because each link counted twice
- growth is quadratic, not linear
basics
~10 sAt most n(n-1)/2, one link per unordered pair of machines. Every machine then reaches degree n-1, so the degree sum is n(n-1), which is twice the link count exactly as the handshake lemma requires.
solid answer
~40 sA simple mesh allows at most one link per unordered pair and no machine links to itself, so the ceiling is the number of pairs: `n(n-1)/2`. Cross-check it with the handshake lemma - every machine sits at the maximum degree `n - 1`, so the degree sum is `n(n-1)`, and halving that gives the same count. The shape of the function is the point: the ceiling grows **quadratically**, so doubling the fleet roughly quadruples the links a full mesh needs. Ten machines allow 45 links; twenty allow 190. A graph is called **dense** when its link count is near that ceiling and **sparse** when it is closer to linear in `n`, and which regime a design sits in decides most of the arguments made about it.
go deeper
Know that a link joins an unordered pair, so the ceiling is the number of pairs and each machine tops out at one fewer than the fleet size. Recall the formula for small cases.
Derive it both ways - counting pairs, and halving the maximum degree sum - and say why the halving is exact. Explain that the ceiling is quadratic, so doubling the fleet roughly quadruples a full mesh.
Use the ceiling and the per-machine degree cap as two quick screens on a plan, and know the two-group variant, where the maximum is the product of the group sizes and rewards an even split.
Decide which regime the design should live in. Full-mesh replication is defensible at small fleet sizes and indefensible as the fleet grows, and the quadratic is the argument that settles it rather than intuition about scale.
## Counting the pairs In a **simple** graph there is no link from a machine to itself and never more than one link between the same pair. A link is therefore fully described by the unordered pair of machines it joins, and the maximum link count is just the number of such pairs: `n(n-1)/2` The derivation is the usual one. Each of the `n` machines could link to `n - 1` others, giving `n(n-1)` ordered choices, but that counts each link twice - once from each end - so halve it. A mesh that actually achieves this ceiling, with every pair joined, is the **complete** graph on `n` vertices. ## The same number from the handshake lemma The lemma gives an independent route, and agreeing answers are worth having: 1. In a simple mesh, no machine can exceed degree `n - 1`, since that is how many distinct peers exist. 2. If every machine is at that ceiling, the degree sum is `n(n-1)`. 3. The degree sum equals twice the link count, so the link count is `n(n-1)/2`. Step 3 also shows why `n(n-1)` is always even and the division is exact: one of two consecutive integers is even. ## What quadratic growth means for a plan | machines | full-mesh links | links per machine | |---|---|---| | 5 | 10 | 4 | | 10 | 45 | 9 | | 20 | 190 | 19 | | 50 | 1,225 | 49 | | 100 | 4,950 | 99 | - The ceiling grows like `n^2 / 2` for large `n`, so **doubling the fleet roughly quadruples** the full-mesh link count. - Per machine, fan-out grows only linearly - each machine gains one peer per machine added - but every machine pays it at once, which is where the quadratic comes from. - **Density** is usually written as the ratio of actual links to the ceiling, `2E / (n(n-1))`: 1 for a full mesh, near 0 for a mesh where each machine keeps a handful of peers. - A design is called **dense** when it sits near the ceiling and **sparse** when its link count stays closer to linear in `n`. Most large meshes are deliberately sparse, and the quadratic is exactly the reason. - The minimum to keep every machine reachable from every other is `n - 1` links, so a connected mesh lives somewhere between `n - 1` and `n(n-1)/2`. ## Splitting the fleet into two groups A common variant restricts links to run only *between* two groups - two racks, two regions - and never within a group. That is a **bipartite** structure, and its ceiling is different: with `a` machines on one side and `b` on the other, every cross pair may be joined and no within-side pair may, so the maximum is the product `a x b`. With the fleet size `n = a + b` fixed, that product is largest when the split is as even as possible, giving `floor(n^2 / 4)`. For twelve machines: - 6 and 6 gives 36 links - the maximum; - 4 and 8 gives 32; - 3 and 9 gives 27; - 1 and 11 gives 11. So a two-group restriction costs roughly half the link ceiling of an unrestricted mesh of the same size - `n^2/4` against `n^2/2` - and the closer the split is to even, the more links the structure can hold. Lopsided splits are the ones that starve. ## Directed links If a replication link is one-way, the object being counted is an *ordered* pair, so the ceiling doubles to `n(n-1)`: each pair may carry a link in each direction. The degree bookkeeping changes to match - out-degrees sum to the link count and in-degrees sum to it separately, rather than both together making twice the count. ## The sanity check this buys Given any proposed wiring plan, two arithmetic screens run in seconds and both come from this material: no stated per-machine degree may exceed `n - 1`, and the total link count may not exceed `n(n-1)/2`. Either breach kills the plan outright. Passing both proves nothing on its own - a plan can respect every ceiling and still be unrealisable - but the screens are free, and they catch the plans that were written without ever checking how many machines there are to link to.
- How does that ceiling change if links may only run between two separate racks?Only cross-rack pairs may be joined, so with `a` machines in one rack and `b` in the other the maximum is the product `a x b`. For a fixed fleet size that product peaks at the evenest split, giving `floor(n^2/4)` - roughly half the unrestricted ceiling. Twelve machines split 6/6 allow 36 links; split 3/9 they allow only 27.
- What is the minimum number of links that still keeps every machine reachable?`n - 1`. Fewer than that leaves the mesh in at least two pieces, and exactly `n - 1` links with everything reachable means the mesh is a tree - no redundant paths, so any single link failure disconnects it. Practical meshes sit above this floor to buy resilience.
- What changes if each replication link is one-way?The ceiling doubles to `n(n-1)`, because an ordered pair can carry a link in each direction. Degrees split too: each machine has an in-degree and an out-degree, and each of those sums to the link count on its own rather than the two together making twice it.
saying these in an interview costs you the question
- Gives n squared, forgetting that pairs are unordered.
- Gives n(n-1) without halving the ordered count.
- Allows a machine to hold degree n, linking to itself.
- Thinks the ceiling grows linearly with fleet size.
- Assumes any lopsided two-group split holds as many links as an even one.