2.2b Groups from graphs

By Frucht’s theorem, evey permutation group is the symmetric group of some finite undirected graph. It is thus possible to construct group from the symmetries of a graph.

Constructing an undirected graph

An undirected graph is simply defined as a set of vertices, joined by a set of edges. In RepLAB, vertices are numbered from 1 to nVertices so that only the total number of vertices matter. Edges are stored as pairs of vertices listed in a matrix.

For instance, the triangle graph can be constructed by

triGraph = replab.UndirectedGraph.fromEdges([1 2; 2 3; 3 1], 3)

triGraph =

Undirected graph with 3 vertices and 3 edges
edges: [1, 2; 1, 3; 2, 3]

Alternatively, a graph can also be constructed from its adjacency matrix:

triGraph = replab.UndirectedGraph.fromAdjacencyMatrix([0 1 1; 1 0 1; 1 1 0])

triGraph =

Undirected graph with 3 vertices and 3 edges
edges: [1, 2; 1, 3; 2, 3]

Graph automorphism

In RepLAB, the symmetry group of a graph is simply obtained by calling the automorphismGroup method:

triGroup = triGraph.automorphismGroup

triGroup =

Permutation group acting on 3 elements of order 6
            identity: [1, 2, 3]
generator(1 or 'x1'): [2, 1, 3]
generator(2 or 'x2'): [1, 3, 2]
    recognize.source: Dihedral group of order 6

The triangle is invariant under any permutation of its vertices. Its automorphism group is thus S_3, which is also identical to the dihedral group of order 6.