Graph Theory

A planar graph is one that can be drawn in a way that no edges cross each other. Try to arrange the following graphs in that way. You will notice that two graphs are not planar. Which ones?

Peterson Graph

The Kuratowski's theorem says, that a graph is planar if, and only if it doesn't contain a subgraph that is a subdivision of K5 or K3,3. We are now using instead the more general theorem of Klaus Wagner and look for minors of K5 and K3,3. On the application below you can see the Petersen graph. Try to find the K5 and K3,3 minor in the Petersen graph. -You can merge vertices that are connected by edges by moving them together and left-clicking them. -You can use the rubber-tool to delete vertices and edges. -To restore the original version press the refresh-button on the right top. -You can rearrange the vertices of the K5 and K3,3 and try to overlap them with the Petersen graph.

Transformation of maps into graphs

Some problems can be solved by converting them into graphs. Do so by following the tasks below. 1) Create the corresponding graph with the same colours as the map is showing. 3) Check the solution and compare it to your result.

Four Colour Theorem

Now that we have created a coloured planar graph lets try to play with it. We know because of the four-colour-theorem, that there is a colouring with only 4 colours possible. Follow the instructions- 1) Try to colour the graph without using cyan. - Select the colour and then a point to change its colour. - You must not colour two adjacent vertices in the same colour 2) Check your result