Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Street signs

      Maths in a minute: Cayley graphs

      Street maps of groups
      Justin Chen
      10 September, 2024

      Imagine you’re trying to solve a Rubik’s cube methodically. To plan out your moves, you might try beginning by writing down your starting position and connecting it to all possible positions which are one move away.

      Image
      rubiks cube graph one layer

      Then, from each of these new positions, you connect them to all possible positions which are one move away.

      Rubiks cube graph two layers

      If you do this repeatedly for every possible position of the Rubik’s cube, you’ll have a complete map of all the positions of the Rubik’s cube, as well as paths connecting any position to any other position using only individual moves. Solving a Rubik’s cube is now the same as finding a path in this map which takes you from your starting position to the solved position! Mathematicians call this map a Cayley graph of the group of permutations of the Rubik’s cube.

      Image
      Rubiks cube full Cayley graph
      Image
      Street signs

      The collection of permutations of a Rubik’s cube is one example of a general mathematical object called a group. We can similarly draw a Cayley graph for any other group. Think of the Cayley graph of a group as a map of all its elements, together with streets along certain allowed directions connecting the different elements.

      Formally, given a group, we pick a subset of group elements to act as allowed directions to move in. In the case of a Rubik’s cube, the allowed directions are all the permutations given by rotating at most one face. Then, we construct a graph (a general name for a collection of nodes, called vertices, and edges connecting them) with one vertex for each group element, and connect two vertices with an edge if we can get from the first vertex to the second by left-multiplying by one of the allowed directions. The resulting graph is known as the Cayley graph of the group.

      Image
      Cayley graph example

      (A technical note: in the case of the Rubik’s cube, the vertices should technically be the set of permutations of the Rubik’s cube. For the sake of the story, we secretly identified each permutation with the position achieved by applying the permutation to the solved cube.)

      Notice that if we pick a different set of allowed directions, we’ll get a different Cayley graph. The vertices would still be the elements of the group, but they would be connected in a different way.

      Cayley graphs are useful because they turn groups from an algebraic object to a geometric one. For example, they give us a notion of distance in a group. Given a group and a specified set of allowed directions, the distance between two elements in the group is the number of steps we have to take in its Cayley graph to get from the first element to the second. For a Rubik’s cube, the distance between two positions is the number of moves we have to make to get from the first position to the second.

      Cayley graphs have given rise to the modern subject of geometric group theory, which draws connections between the algebra of groups and the geometry of their Cayley graphs. For more about this active field of research, see here:

      Groups, geometry, and Gromov — Find out about the proof that started the modern field of geometric group theory.

      • Log in or register to post comments

      You might also like

      blog

      Maths in three minutes: Groups

      Capturing symmetry with algebra.
      article

      Groups, geometry and Gromov

      Read more about...

      geometric group theory
      group theory
      graph theory
      algebra
      University of Cambridge logo

      Plus is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms