# Graphs and NetworksPlanar Graphs

Here is another puzzle that is related to graph theory.

In a small village there are three utility plants producing water, electricity and gas respectively. There are also three houses which need to be served. Unfortunately, due to the city’s layout, the pipes or cables for every product are not allowed to cross.

Try to connect each of the plants below to each of the houses, without any of your lines crossing:

Just like the Königsberg bridges before, you quickly discover that this problem is also impossible. It seems that some graphs can be drawn without overlapping edges – these are called **planar graphs** – but others cannot.

The

The graph in the three utilities puzzle is the

### Planarity

This is a planar graph, but the