Log in to Mathigon

Google
Create New Account

Reset Password     

Share

Change Language

EnglishVietnamese

Send us Feedback

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

Are you sure that you want to reset your progress, response and chat data for all sections in this course? This action cannot be undone.

Glossary

Select one of the keywords on the left…

Graphs and NetworksPlanar Graphs

Reveal All Steps

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.

K3 is planar.

K4 is planaris not planar.

K5 is not planaris planar.

The complete graph K5 is the smallest graph that is not planar. Any other graph that contains K5 as a subgraph in some way is also not planar. This includes K6, K7, and all larger complete graphs.

The graph in the three utilities puzzle is the bipartite graph K3,3. It turns out that any non-planar graph must contain a K5 or a K3,3 or a subdivision of these two graphs as a subgraph.

Planarity

This is a planar graph, but the ${n} vertices have been scrambled up. Rearrange the vertices so that none of the edges overlap.