Discrete Mathematics
# Graph Theory

Is this graph planar?

Is this graph planar?

Suppose that there are three houses \(A, B, C\) and three utilities 1, 2, and 3 each of which needs to be connected by a wire to all three houses. Assuming the utilities and the houses are all points (nodes), is there a way to position them and the wires (edges) such that no two wires overlap?

Note: this is the same as asking whether \(K_{3,3}\) is a planar graph.

×

Problem Loading...

Note Loading...

Set Loading...