Graphs can, of course, be used to model all sorts of problems in various areas of discrete mathematics. So it’s worthwhile to look at what *Magma* can do with graphs. Let’s suppose you just wanted to create a small graph with just a few edges. You can do this by telling *Magma* the order (number of vertices) and then listing the edges as unordered pairs:

` > G := Graph<5 | {1,3},{1,4},{1,5},{2,3},{2,4},{2,5}>;`

` > G;`

` Graph`

` Vertex Neighbours`

` 1 3 4 5 ;`

` 2 3 4 5 ;`

` 3 1 2 ;`

` 4 1 2 ;`

` 5 1 2 ;`

Once we have the graph, we can ask Magma for properties of it:

` > IsBipartite(G);`

` true`

` > VertexConnectivity(G);`

` 2`

` > ChromaticNumber(G);`

` 2`

` > IsPlanar(G);`

` true`

Let’s check if Magma knows Kuratowski’s Theorem for planar graphs. Here I’ll define *G* to be the complete bipartite graph *K*_{3,3} and then ask if the graph is planar. *Magma* can even try to solve problems which are NP-hard (such as the clique number for a graph), although for larger graphs it might take a while.

` > G := Graph<6 | {1,4},{1,5},{1,6},{2,4},{2,5},{2,6},{3,4},{3,5},{3,6}>;`

` > IsPlanar(G);`

` false`

` > CliqueNumber(G);`

` 2`

** Exercise:** Define G to be the Peterson Graph on 10 vertices. You might first draw a picture of the Peterson Graph and then figure out how to list the edges (there are 10 vertices). Google it if you don’t know what it looks like.

- Determine its chromatic number.
- Determine whether or not the graph is planar.