A wiring plan gives each of seven machines exactly three replication links - why can no such mesh exist?
answer
- add the stated degrees first
- seven threes is an odd total
- compare the total against twice something
- odd degrees have to pair up
- parity rules the plan out entirely
basics
~20 sThe degrees would sum to 7 x 3 = 21, which is odd, but every graph's degree sum equals twice its edge count and so must be even. The plan is impossible for any wiring, not just awkward ones.
solid answer
~40 sAdd the plan's degrees: seven machines at three links each gives 21. The handshake lemma says the degree sum equals `2E`, which is even, and 21 is not - so 21 is not `2E` for any whole number of links and no mesh realises the plan. The general form is the parity corollary: **the number of odd-degree vertices is always even**. Three is odd, and here seven machines carry it, which is an odd count of odd degrees. The fix is arithmetic, not topological: change the machine count to an even number, or change the per-machine degree to an even one. Six machines at three links each sums to 18, so nine links, and such a mesh does exist.
go deeper
Add the stated per-machine link counts before anything else. If the total is odd, the plan cannot be realised, because that total always equals twice the number of links.
State the corollary rather than the arithmetic instance: the number of odd-degree machines is always even. Be able to say which two conditions decide whether a uniform k-link-per-machine mesh exists on n machines.
Turn the refutation into options - raise the fan-out, raise the machine count, or give up uniformity - and name what each costs. Say explicitly that an even total only clears the screen, it does not certify the plan.
The interesting judgment is which dial the fleet can afford to move, and whether uniform fan-out was ever the real requirement. Breaking regularity is cheap in links and expensive in the hot spot it creates.
## The one-line refutation Seven machines, three links each. Total degree `= 7 x 3 = 21`. The handshake lemma says the degree sum equals `2E`, twice the number of links, which is even for every whole `E`. No whole number doubles to 21, so the plan cannot be built - not by a clever layout, not by allowing the mesh to be disconnected, not by any arrangement at all. This is the smallest example in the branch of mathematics closing a design question before any design work starts. ## Why parity is the general tool Split the machines into those with even degree and those with odd degree. The even-degree group contributes an even amount to the total, whatever its size. So the parity of the whole degree sum is decided entirely by the odd-degree group. Since the total must be even, that group must contain an **even number of machines**. This is the parity corollary of the handshake lemma, and it is the form worth carrying: - there is no graph with exactly one odd-degree vertex; - there is no graph with exactly three, or five, or any odd number of them; - a plan that names an odd count of machines each carrying an odd number of links is dead on arrival; - a plan that names an even count of odd-degree machines has cleared this check and nothing more. That last bullet matters. Parity is a **necessary** condition, never a sufficient one. Clearing it says only that the arithmetic does not forbid the plan. ## The regular-mesh rule A mesh where every machine has the same degree `k` is **k-regular**. Two conditions decide whether one exists on `n` machines as a simple graph - no self-links, no duplicate links: 1. `k <= n - 1`, because a machine has only `n - 1` distinct peers it could link to; 2. `n x k` is even, because that product is the degree sum and must equal `2E`. For simple undirected graphs those two conditions together are also enough: whenever both hold, such a mesh can be built. Worked through the near misses: | plan | degree sum | verdict | |---|---|---| | 7 machines, 3 links each | 21 | impossible - the sum is odd | | 6 machines, 3 links each | 18 | buildable - 9 links | | 9 machines, 3 links each | 27 | impossible - the sum is odd | | 5 machines, 4 links each | 20 | buildable - 10 links, every pair joined | | 5 machines, 5 links each | 25 | impossible twice over - odd sum, and 5 exceeds the 4 available peers | Notice that an odd machine count is not itself the problem. Nine machines at **four** links each sums to 36, which is fine. The obstruction is the product's parity: an odd degree demands an even number of machines to carry it. ## Reading the failure the right way There are two ways to repair the seven-machine plan, and they are genuinely different engineering choices: - **Change the degree.** Seven machines at four links each gives a sum of 28 and therefore 14 links. Fan-out rises. - **Change the machine count.** Eight machines at three links each gives 24 and therefore 12 links. Fleet size rises, fan-out holds. - **Break regularity.** Six machines at three links and one at four sums to 22, so 11 links. The mesh is no longer uniform, and one machine now carries more replication traffic than its peers - which is usually the thing the uniform plan was trying to avoid. A weak answer stops at 'it is impossible'. The useful answer names which of those three dials the plan can afford to move. ## Where the same argument reappears The parity corollary is the load-bearing step in several results that look unrelated at first sight. The classic one is traversability: a connected graph has a closed tour using every edge exactly once only when every degree is even, and an open one exactly when precisely **two** degrees are odd. Two, not one and not three - and the reason it can never be one or three is this same corollary. Any time a result says 'exactly two odd vertices', parity is doing the work underneath.
- Which changes to the plan make it buildable?Move either factor to make the product even. Eight machines at three links each sums to 24, so 12 links. Seven machines at four links each sums to 28, so 14 links. Or abandon uniformity: six machines at three and one at four sums to 22, giving 11 links, at the cost of one machine carrying extra replication traffic.
- Does an even degree sum guarantee the plan can be built?No - it is necessary, not sufficient. Four machines with degrees 3, 3, 3 and 1 sum to 10, an even total, yet no simple graph realises it: three machines of degree 3 on four vertices must each link to all the others, which forces the fourth to degree 3 rather than 1.
- Why can a graph never have exactly one vertex of odd degree?The even-degree vertices contribute an even amount to the degree sum whatever their number, so the odd-degree vertices alone decide the total's parity. One odd degree makes the total odd, which contradicts the sum being twice the edge count. Odd degrees must therefore come in pairs.
saying these in an interview costs you the question
- Says it is merely hard to wire rather than impossible.
- Blames the odd number of machines instead of the product's parity.
- Thinks allowing a disconnected mesh rescues the plan.
- Claims an even degree sum guarantees the plan is buildable.
- Asserts a graph can have exactly one odd-degree vertex.
- Tries to fix it by adding a self-link, which still adds two.