Graph Theory

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;
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);
> VertexConnectivity(G);
> ChromaticNumber(G);
> IsPlanar(G);

Let’s check if Magma knows Kuratowski’s Theorem for planar graphs. Here I’ll define G to be the complete bipartite graph K3,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);
> CliqueNumber(G);

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.

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