skip to content

Why does a mesh diagram that can be drawn with no crossing links hold at most 3V - 6 links?

level: seniorimportance: nice to knowfreq 24%

answer

  1. count regions, including the outer one
  2. machines minus links plus faces
  3. each link borders exactly two regions
  4. no region has fewer than three sides
  5. the ceiling turns out linear

basics

~20 s

A crossing-free drawing satisfies Euler's formula V - E + F = 2, and every face needs at least three link-sides while each link borders two faces. Combining the two caps links at 3V - 6, so such diagrams stay sparse.

solid answer

~40 s

Draw the mesh in the plane with no crossings and the drawing cuts the plane into faces, with **Euler's formula** `V - E + F = 2` relating machines, links and faces - the unbounded outer region counts as a face. In a simple mesh with at least three machines, every face is bounded by at least three link-sides, and each link borders exactly two faces, so `3F <= 2E`. Substituting `F <= 2E/3` into Euler's formula gives `E <= 3V - 6`. The consequence is that a crossing-free layout is forced to be **sparse** - average degree below 6, and always some machine with five peers or fewer - which is a linear ceiling, nowhere near the quadratic ceiling an unrestricted mesh allows.

go deeper

for a junior

Know that a crossing-free drawing satisfies machines minus links plus regions equals two, with the outer region counted, and that this forces such drawings to stay sparse.

for a middle

Give the idea of the derivation: each link borders two regions, each region needs at least three link-sides, and combining that with Euler's formula caps links at three times the machine count minus six.

for a senior

Use the bound in the only direction it works - to refute - and reach for the tighter triangle-free version when no three machines are mutually linked, since the general bound misses those cases entirely.

for a principal

Treat a crossing-free requirement as a hard linear ceiling on fan-out, and decide whether the layout constraint is worth what it costs in link budget before anyone starts rearranging the diagram.

## What the bound is about Suppose a proposed replication mesh has to be drawn - on a diagram, a floor plan, a physical cable tray - so that no two links cross. A graph that admits such a drawing is **planar**. The claim is that planarity alone caps the link count at `3V - 6`, independently of how the machines are arranged. ## Euler's formula A crossing-free drawing of a connected graph divides the plane into **faces**: the bounded regions plus the one unbounded outer region, which counts. Euler's formula states `V - E + F = 2` for every such drawing. A useful sanity check: four machines wired into a square give `V = 4`, `E = 4`, one inside face and one outside, so `F = 2`, and `4 - 4 + 2 = 2`. Add a diagonal and both `E` and `F` rise by one, leaving the total unchanged - which is the general pattern, and why the formula does not depend on the drawing chosen. ## The idea of the argument The bound comes from counting *link-sides* - the incidences between links and faces - two ways: 1. Each link has two sides, so it borders exactly two faces. Totalling over links gives `2E` incidences. 2. In a simple graph with at least three machines, no face can be bounded by fewer than three link-sides: two links between the same pair would be a duplicate, and one link alone encloses nothing. Totalling over faces gives at least `3F`. 3. Therefore `3F <= 2E`, that is `F <= 2E/3`. 4. Substitute into Euler's formula: `2 = V - E + F <= V - E + 2E/3 = V - E/3`, which rearranges to `E <= 3V - 6`. The same double-count shape as the handshake lemma is doing the work again - one set of objects, two totals, and the inequality falls out. ## What the bound forces - The ceiling is **linear** in the machine count, not quadratic. Twenty machines allow at most 54 crossing-free links, against 190 for an unrestricted mesh. - The degree sum is at most `2(3V - 6) = 6V - 12`, so the **average degree is below 6**. - Consequently every planar mesh contains at least one machine with **degree 5 or less**. Averages guarantee a minimum below them; this one is used constantly as the induction step in colouring arguments. - A disconnected drawing has strictly fewer links than a connected one on the same machines, so the bound holds for every simple planar graph with `V >= 3`, connected or not. ## The direction of the test This is the part that gets misused. The implication runs one way only: | observation | what it proves | |---|---| | `E > 3V - 6` | the graph is definitely **not** planar | | `E <= 3V - 6` | **nothing** - it may or may not be planar | Five machines with every pair linked have `V = 5` and `E = 10`, while `3(5) - 6 = 9`. Ten exceeds nine, so no crossing-free drawing exists - a complete mesh of five machines cannot be laid out without a crossing. The converse trap: six machines split into two groups of three with all nine cross-group links has `V = 6` and `E = 9`, against a bound of `3(6) - 6 = 12`. It passes comfortably, and it is still not planar. Passing `3V - 6` is not a certificate. ## The tighter bound when there are no triangles The six-machine case above is caught by a refinement. If the mesh has **no triangles** - no three machines mutually linked, which is automatic when links only run between two groups - then no face can be bounded by three sides; the shortest cycle has length four. Redo the count with `4F <= 2E`: `2 = V - E + F <= V - E + E/2 = V - E/2`, giving `E <= 2V - 4`. For that graph, `2(6) - 4 = 8`, and it has 9 links. Nine exceeds eight, so it is not planar after all - the general bound was simply too loose to see it. Applying `3V - 6` to a triangle-free graph and concluding 'planar' is the most common error with this material. ## Where it lands in practice The bound is the reason a crossing-free layout is a real constraint rather than a cosmetic preference: it forces sparsity by a linear ceiling, and beyond a handful of peers per machine no such layout exists. When a diagram of a proposed mesh refuses to come out clean, the honest first check is arithmetic - count `V` and `E` - rather than another attempt at rearranging the boxes.

  • If a mesh satisfies E <= 3V - 6, does that prove it can be drawn without crossings?
    No - the implication runs one way. Exceeding the bound proves non-planarity; respecting it proves nothing. Six machines in two groups of three with all nine cross-group links satisfy the bound of 12 and are still not drawable without a crossing; the tighter triangle-free bound of `2V - 4`, which gives 8 here, is what catches them.
  • Why does every planar mesh contain a machine with at most five peers?
    The degree sum is twice the link count, so at most `6V - 12`, making the average degree strictly below 6. No set of numbers has every member above its own average, so some machine has degree 5 or less. That guaranteed low-degree machine is the standard induction step in planar colouring arguments.
  • Why does the outer region count as a face in Euler's formula?
    Because the count is of regions the drawing cuts the plane into, and the unbounded region is one of them. Omitting it gives `V - E + F = 1` and breaks every derivation built on the formula. A single square drawn in the plane has two faces, inside and outside, not one.

saying these in an interview costs you the question

  • Forgets the unbounded outer region when counting faces.
  • Reads the bound as proof of planarity rather than a refutation.
  • Applies 3V - 6 to a triangle-free graph instead of 2V - 4.
  • Thinks the ceiling grows quadratically like an unrestricted mesh.
  • Claims Euler's formula depends on how the drawing is arranged.
  • Believes any graph can be drawn crossing-free with enough rearranging.