Why connectivity cannot be decided without looking at every edge

Why connectivity cannot be decided without looking at every edge

Two graphs on 8 vertices that differ in one edge. Any algorithm that has not examined that edge has seen exactly the same thing in both cases and must give the same answer, and the answers differ — the left graph is connected and the right is not. An adversary who watches which edges have been examined can always arrange for the undecided edge to be one of them, so every correct algorithm examines all E of them. This is a lower bound with nothing counted in it: it comes from what the algorithm has not seen.

Drawn at 690 × 400, wide on the page. Everything above is what adversary-edges returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

2 essays call adversary-edges. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.