So a classic problem that wasted hours of my life when I was younger:

You have three houses: A, B, and C. Your goal is to connect them to three utilities: Water, Gas, and Electricity (W, G, and E)… but none of the lines can cross. It turns out this is impossible if all 6 nodes are in a plane. Go ahead, try it out, I’ll wait. Here, here’s somewhere to practice:

W G E

A B C

so the reason is that the graph K_{3,3} (the bipartite graph we’d achieve if this was doable) is not planar. The proof of this relies on Euler’s theorem for planar graphs, which says that for any planar graph

R + N - E = 2

where
R is the number of closed regions
N is the number of nodes
E is the number of edges

For K_{3,3}, clearly N=6 and E=9, so we would need to have R=5. A closed region is an area bounded by a cycle. For example, if we were to connect A–W–B–E–A that would give us one region.

So, suppose there were 5 regions in K_{3,3}. First, notice that we don’t get a region with a cycle with two edges, since that simply means we used the same edge twice. Also, there are no odd cycles in a bipartite graph, so any region must be bounded by a cycle of at least 4 edges. However, each edge will be a member of a cycle for two regions (one on each side) so this means that we need 5*4/2 = 10 edges in order to have 5 regions. We only have 9 in K_{3,3} so this is impossible.

http://www.cut-the-knot.org/do_you_know/3Utilities.shtml