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.
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. Inclusion test: Require a simple graph isomorphic to K3,3, with two three-vertex parts and all nine possible cross-part edges. Exclusion test: Exclude the verbal puzzle without its full incidence pattern, drawings with accidental crossings, K3,2, and networks missing or adding edges. Nearest boundary: The three-utilities problem is the puzzle narrative; the utility graph is the abstract K3,3 structure that explains its planar impossibility. Exit condition: The identity ends when either part has another size or the complete cross-connection relation is changed. Common misclassifications: 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. Nearest named distinctions: Three Utilities Problem: The puzzle is an application; the utility graph is its K3,3 formalization. K5: The other classical Kuratowski obstruction has five mutually adjacent vertices. K3,2: It has only six cross-edges and lacks the same planar obstruction. Utility Network: A real infrastructure system need not have complete bipartite incidence.
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.
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.
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