In a replication mesh where each link joins two machines, why does the sum of machines' link counts equal twice the link count?
answer
- count ends, not whole links
- each link touches exactly two machines
- one set of objects, two totals
- parity falls out of the total
- degree total never comes out odd
basics
~20 sEvery link has two ends, and each end raises exactly one machine's link count by one. Totalling link counts therefore counts every link twice. This is the handshake lemma: the degree sum equals 2E, so it is always even.
solid answer
~40 sModel each machine as a vertex and each replication link as an edge; a machine's **degree** is how many link-ends it carries. The handshake lemma is a double count of one set: the set of link-ends. Walk the links and you find `2E` ends, since each link has exactly two. Walk the machines and you find the degree sum. Both totals count the same objects, so the degree sum is `2E`. Two consequences do real work: the degree sum can never be odd, and the average number of links per machine is `2E/V`. So a proposed wiring plan whose per-machine counts add to an odd number is not merely awkward to build - no mesh realises it at all.
go deeper
Recall the identity in one line: total link-ends equals twice the number of links, because every link has two ends. Be able to state that the degree total is therefore always even.
Explain it as a double count of link-ends rather than quoting it, and state what changes under self-links, parallel links and one-way links. Derive the average fan-out as twice the link count over the machine count.
Use it as a screen on a real plan: halve the stated degree total to get the link budget, reject an odd total outright, and be clear that passing the screen does not prove the plan is buildable.
Know when the model itself is the decision: whether links are one-way changes which identity applies and therefore which capacity numbers a plan should be judged against. Choosing the wrong model quietly halves or doubles the budget.
## What a degree counts Model a peer-to-peer replication mesh as a graph: each machine is a **vertex**, each bidirectional replication link is an **edge**. The **degree** of a machine is the number of *link-ends* attached to it. In a **simple** graph - no link from a machine to itself, never two links between the same pair - degree also equals the number of distinct peers, which is why the two ideas get conflated. The link-end reading is the one that survives every convention, so prefer it. ## The double count The **handshake lemma** states that the sum of all degrees equals twice the number of edges. The argument is a *double count*: pick one set of objects and total it two different ways. 1. Take the set of all link-ends. Every link contributes exactly two ends, so walking the links gives `2E` ends. 2. Walk the machines instead. Each machine reports its own degree, so this walk gives the degree sum. 3. Both walks enumerate the same set of link-ends without omission or repetition, so the two totals are equal: degree sum `= 2E`. Nothing in that argument depends on the mesh being connected, on the links being placed sensibly, or on any machine's degree in particular. It is pure bookkeeping, which is exactly why it is safe to lean on during a design review. ## What the lemma forces - The degree sum is **even**, in every graph, always. There is no wiring, however exotic, that makes it odd. - The number of machines with an **odd** degree is even - odd values have to pair up for the total to come out even. - The **average** degree is `2E/V`. Ask for the average number of peers per machine and you are really asking for this ratio. - Adding one link raises exactly **two** degrees by one each, so the degree sum moves in steps of two. - In a simple mesh no degree exceeds `V - 1`, because a machine has only that many distinct peers available. ## Conventions that change the arithmetic The lemma is stable, but what one link contributes depends on the structure you chose to model with: | structure | what one link contributes | resulting identity | |---|---|---| | ordinary undirected link | one to each of two endpoints | degree sum = `2E` | | self-link (loop) | two to its single endpoint | degree sum = `2E` | | parallel links between one pair | one to each endpoint, per link | degree sum = `2E` | | directed link | one out-degree, one in-degree | out-sum = in-sum = `E` | The self-link row is the one people get wrong. A loop is drawn once, so it looks like it should add one - but it attaches **both** of its ends to the same machine, so it adds two. That convention exists precisely to keep the lemma true; abandon it and the identity breaks for no gain. The directed row is worth internalising separately. Once links carry a direction, there is no single degree per machine: there is an in-degree and an out-degree, and each *individually* sums to `E` rather than `2E`. If replication in your mesh is one-way per link, that is the identity to quote. ## Using it on a wiring plan The practical move is to treat the degree sum as a cheap screen before anyone reasons about topology. Given a plan that states how many peers each machine should end up with: - add the numbers up; if the total is odd, stop - the plan is unrealisable and no amount of rearranging helps; - if the total is even, it equals `2E`, so halve it to learn how many links the plan actually requires, which is usually the number someone wanted for capacity planning anyway; - divide by the machine count for the average fan-out, and compare it against the ceiling `V - 1`. None of this proves the plan *is* buildable - an even sum is necessary, not sufficient, and a plan can clear it and still fail for structural reasons. But it is a one-line check that kills a whole family of bad plans, and it is the reason this lemma shows up in interviews at all: it is the smallest example of an argument that constrains a design before the design exists. ## The name The lemma is called the handshake lemma because of its oldest phrasing: in any room, the total number of hands shaken, counted per person, is twice the number of handshakes - since each handshake involves exactly two people.
- Does the identity still hold when a machine has a link to itself?Yes, by convention a self-link adds two to its own machine's degree, because both of its ends attach there. That convention exists to keep the degree sum equal to twice the edge count; the lemma is unchanged, and the degree sum stays even.
- What does the lemma say about the average number of peers per machine?The average degree is the degree sum divided by the machine count, so it equals `2E/V`. A mesh of 50 machines and 120 links averages 4.8 peers each. The average alone says nothing about the spread - one machine may still carry far more links than the average.
- How does the identity change if replication links are one-way?There is no single degree per machine any more. Each directed link adds one out-degree at its source and one in-degree at its target, so the out-degrees sum to `E` and the in-degrees sum to `E` separately - not `2E`. Adding the two sums back together recovers `2E`.
Count the plugged-in cable ends at the back of a rack instead of the cables. Every cable has two ends, so the end count is always exactly double the cable count.
saying these in an interview costs you the question
- Says the degree sum equals the number of links.
- Counts a self-link as adding one to a machine's degree.
- Thinks the identity needs the mesh to be connected.
- Confuses the degree sum with the number of machines.
- Claims an odd degree sum is possible in some layouts.
- Treats degree as the count of machines reachable, not links attached.