Utility Graph — Definition, Formula & Examples

The utility graph is the complete bipartite graph

K_{3,3}

, formed by connecting each of three "utility" vertices to each of three "house" vertices, giving 9 edges total. It is famous as the smallest example showing that not every graph can be drawn in a plane without edge crossings.

The utility graph $K_{3,3}$ is the complete bipartite graph whose vertex set is partitioned into two disjoint sets $A = \{a_1, a_2, a_3\}$ and $B = \{b_1, b_2, b_3\}$ , with an edge joining every vertex in $A$ to every vertex in $B$ . By Kuratowski's theorem, $K_{3,3}$ is one of two fundamental nonplanar graphs (the other being $K_5$ ).

How It Works

The classic puzzle asks: can you connect three houses to three utilities (water, gas, electricity) so that no pipes cross? You draw 6 vertices arranged in two rows of 3 and try to connect every top vertex to every bottom vertex without any edges intersecting. No matter how you rearrange the drawing, at least two edges must cross. This impossibility is guaranteed by the fact that

K_{3,3}

is nonplanar, which can be verified using Euler's formula for planar graphs.

Worked Example

Problem: Use Euler's formula to prove the utility graph K₃,₃ cannot be planar.

Step 1: Count vertices and edges.

K_{3,3}

has

v = 6

vertices and

e = 3 \times 3 = 9

edges.

v = 6, \quad e = 9

Step 2: For a connected planar graph, Euler's formula gives

v - e + f = 2

, so the number of faces would be

f = 2 - v + e = 2 - 6 + 9 = 5

f = 2 - 6 + 9 = 5

Step 3: Since

K_{3,3}

is bipartite, it has no odd cycles, so every face is bounded by at least 4 edges. Each edge borders at most 2 faces, so

4f \leq 2e

. Check:

4(5) = 20

but

2(9) = 18

. Since

20 > 18

, we have a contradiction.

4f = 20 > 18 = 2e \quad \Rightarrow \quad \text{contradiction}

Answer:

K_{3,3}

cannot be drawn in the plane without edge crossings; it is nonplanar.

Why It Matters

Kuratowski's theorem states that a graph is nonplanar if and only if it contains a subdivision of

K_{3,3}

K_5

. This makes the utility graph a cornerstone test case in circuit board design, network layout, and any problem where crossing-free embedding matters.

Common Mistakes

Mistake: Believing that because one particular drawing of K₃,₃ has crossings, you just haven't tried hard enough to find a crossing-free drawing.

Correction: Nonplanarity is a proven mathematical property of the graph itself, not a limitation of any single drawing. No rearrangement of vertices will eliminate all crossings.