Utility graph¶
The complete bipartite graph K3,3, whose two sets of three vertices and nine cross-edges encode the nonplanar three-utilities puzzle.
Core Idea¶
The utility graph forgets the story's pipes and houses while preserving its incidence demand: three vertices on each side, with every vertex on one side adjacent to every vertex on the other. It has six vertices, nine edges, degree three at every vertex, and no triangles.
Its significance is topological. K3,3 cannot be embedded in the plane without edge crossings, although it can embed on other surfaces. The impossibility concerns the abstract graph and surface, not a particular poorly drawn diagram.
Structural Signature¶
Sig role-phrases:
- First vertex part — Contains the three houses or one side of the bipartition. It is carrier. Counterfactual: Changing its size changes the complete bipartite graph.
- Second vertex part — Contains the three utilities or opposing part. It is carrier. Counterfactual: Mixing the parts destroys the puzzle interpretation.
- Nine cross-edges — Join every vertex in one part to every vertex in the other. It is relation. Counterfactual: Omitting one connection can make the puzzle planar.
- No within-part edge — Maintains bipartite structure and triangle freedom. It is constraint. Counterfactual: Adding house-to-house edges creates another graph.
- Embedding surface — Determines whether edges can meet only at common endpoints. It is setting. Counterfactual: Nonplanarity is specific to the plane or sphere.
- Graph isomorphism — Preserves the K3,3 identity across labels and drawings. It is invariant. Counterfactual: A tangled picture does not prove a different graph.
What It Is Not¶
- It is not every network of public utilities.
- It is not a drawing merely containing three crossings.
- It is not K3,2 or another incomplete bipartite graph.
- It is not the puzzle narrative apart from its graph.
- Closest near-miss. The three-utilities problem is the puzzle narrative; the utility graph is the abstract K3,3 structure that explains its planar impossibility.
Scope of Application¶
- Graph theory. Provides a standard small cubic bipartite graph.
- Planarity. Supplies one of the two Kuratowski obstruction types.
- Topological embeddings. Compares behavior on plane, torus, and other surfaces.
- Puzzle analysis. Proves why nine noncrossing connections are impossible.
- Rigidity studies. Uses K3,3 as a small minimally rigid nonplanar example.
Clarity¶
Identify the two vertex parts, enumerate all nine required adjacencies, rule out loops and within-part edges, and state the embedding surface. Distinguish graph isomorphism from visual layout.
Manages Complexity¶
K3,3 compresses a spatial puzzle into finite incidence data. Euler-type arguments and forbidden-minor results can then prove impossibility without testing every drawing.
Abstract Reasoning¶
- Translate houses and utilities into separate vertex parts.
- Add an edge for every required house–utility pair.
- Verify that the resulting graph is K3,3.
- Declare the surface and crossing rules.
- Apply planarity or embedding theorems.
- Interpret the result back in the puzzle only after the graph assumptions are checked.
Knowledge Transfer¶
The transferable cargo is complete bipartite incidence separated from its drawing. It transfers across routing stories when two three-member classes require all cross-connections; different class sizes or surfaces yield other problems.
Examples¶
Canonical¶
Three house vertices and three utility vertices are joined pairwise across the partition, giving each vertex degree three.
Mapped back: parts → 3+3; edges → 9.
Applied / In Practice¶
The same K3,3 incidence structure embeds without crossings on a torus, showing that graph identity persists while surface feasibility changes.
Mapped back: graph → K3,3; surface → torus.
Applied / In Practice¶
Three houses connected to only two utilities form K3,2 and can be drawn in the plane without the same obstruction.
Mapped back: parts → 3+2.
Structural Tensions¶
T1 — Abstract Graph versus Particular Drawing. K3,3 remains one graph across many layouts, while crossings depend on embedding.
Diagnostic: Is the claim combinatorial or geometric?
T2 — Plane Impossibility versus Surface Solvability. A torus or projective surface changes available routes.
Diagnostic: Which surface is part of the problem?
T3 — Complete Demand versus Edge Deletion. The impossibility relies on all nine connections; removing an edge alters the obstruction.
Diagnostic: Are all cross-part pairs required?
Structural–Framed Character¶
Utility Graph is structural: its identity is K3,3 incidence, while the utility story and chosen embedding surface supply the frame.
Structural Core vs. Domain Accent¶
The core is a complete two-part graph with part sizes three and three. Topological graph theory supplies plane embeddings, crossings, Euler bounds, subdivisions, forbidden minors, genus, and rigidity properties.
Instantiates / Related Primes¶
This entry is a kind of Network.
-
Approved root. The frozen review did not authorize a live complete-bipartite-graph parent.
-
Related — bipartite graph, complete graph, planarity, Kuratowski theorem, graph embedding, and crossing number. These state its class and uses.
Relationships to Other Abstractions¶
Current abstraction Utility graph Domain-specific
Parents (1) — more general patterns this builds on
-
Utility graph is a kind of Network Prime
Utility graph is a domain-specific kind of network under its frozen identity and differentia.Utility graph is a domain-specific kind of network under its frozen identity and differentia.
Hierarchy path (1) — routes to 1 parentless root
- Utility graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance
Neighborhood in Abstraction Space¶
Utility graph sits in a crowded region of the domain-specific corpus (27th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Graph Structures & Algorithms (24 abstractions)
Nearest neighbors
- Complete Bipartite Graph — 0.91
- Loop (Graph Theory) — 0.90
- Prism graph — 0.90
- Digon — 0.89
- Prim’s Algorithm — 0.88
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Three Utilities Problem. Tell: The puzzle is an application; the utility graph is its K3,3 formalization.
- K5. Tell: The other classical Kuratowski obstruction has five mutually adjacent vertices.
- K3,2. Tell: It has only six cross-edges and lacks the same planar obstruction.
- Utility Network. Tell: A real infrastructure system need not have complete bipartite incidence.
References¶
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Three_utilities_problem (revision 1337576115).
- Preserved source candidate: https://books.google.com/books?id=yLSTwH0pINIC&q=%22three+houses+and+three+wells%22
- Preserved source candidate: https://books.google.com/books?id=w8tPAQAAMAAJ&pg=PA392
- Preserved source candidate: https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA23
- Preserved source candidate: https://gdz.sub.uni-goettingen.de/id/PPN599484047_0029?tify=%7B%22pages%22%3A%5B5%5D%7D
- Preserved source candidate: https://archive.org/stream/TheStrandMagazineAnIllustratedMonthly/TheStrandMagazine1913bVol.XlviJul-dec#page/n119/mode/2up
- Preserved source candidate: https://archive.org/stream/amusementsinmath00dude#page/72
- Preserved source candidate: https://archive.org/details/amusementsinmath00dude/page/200
- Preserved source candidate: https://books.google.com/books?id=kbI_AQAAMAAJ&pg=PA276
The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.