On this page we look at some of the mathematical theories that supported codebreaking:

Bill+Tutte+-+SquareThe Squared Square

Tutte’s success in code breaking was attributed to his love of mathematical puzzles developed while he was at Cambridge University, where he was among the first to prove a solution to the problem of Squaring the Square.

It was this that led to him being invited to join Bletchley Park in 1941. The Squared Square is recognisable to mathematicians worldwide.

For further information see – https://www.srcf.ucam.org/tms/about-the-tms/the-squared-square/#1

Graph Theory

Graph Theory is the mathematical study of collections of objects with links between them.  The focus is not on the objects themselves but on the structure formed by the links among the objects.  There are examples of linked collections of objects everywhere: road networks, the World Wide Web, social networks, communications networks, molecules, maps etc.

In graph theory, the objects are called vertices (or nodes), and the links between pairs of objects are called edges (or arcs).  A graph is just a collection of vertices together with some edges.  For example:

  • Road networks: the vertices are towns; the edges are the roads between towns. 
  • The World Wide Web: the vertices are webpages, and the edges are the hyperlinks that take you from one webpage to another.
  • Social networks: the vertices are people; the edges are the friendships between people.
  • Phone communication networks: the vertices are phones; the edges are the phone calls.
  • Molecules: the vertices are atoms; the edges are the bonds between the atoms.

We often draw pictures of graphs.  Vertices are drawn as points, and edges are drawn as lines or curves between points.  A single graph can be drawn in many different ways.

The objects and links listed above are very diverse in nature, but when viewed just as graphs, we can ask the same mathematical questions about each of them.

  • Is there a way of going from one vertex to another by moving along some path made of edges?  A path may be just a single edge, if the two vertices have an edge linking them, or it may be a longer chain of edges, if the vertices are more distant.  If we can do this, then the two vertices are connected.
  • Can we do a “round trip” from some vertex, going along edges, never repeating a vertex until we get back to the start?  This is called a circuit.
  • Is there such a round trip that includes every vertex in the graph?  This is called a Hamiltonian circuit.
  • How can we break the graph into smaller pieces by removing as few vertices as possible?  This is about connectivity.
  • What is the largest set of vertices in the graph that has no edges between any two of them?  A set of vertices with no edge joining any two of them is called an independent set.
  • When can we find a set of edges in a graph such that every vertex meets exactly one of these edges?  Such a set of edges is called a perfect matching.
  • When can a graph be drawn on a flat surface (i.e., the plane) without any edge crossings?  Such a graph is called planar.
  • Given a graph and a set of colours, can we give each vertex a colour in such a way that vertices joined by an edge always get different colours?  This is about colouring.
  • When are two graphs really the same, apart from the names used for their vertices and edges?  In other words, can we rename the vertices and edges of one graph so that it becomes identical to the other?  If this can be done, then we say that the two graphs are isomorphic.

These are the kinds of questions we study in graph theory.  Each question is really part of a family of questions:

  • Existence (does a structure of some particular type exist?)
  • Searching (how can we find such a structure, in a systematic way, and how long will it take us to do so?)
  • Optimisation (how large or small can these structures be, in a given graph, and how do we find the largest/smallest?)
  • Counting (how many such structures are there?).

By making our graphs abstract — i.e., by forgetting all the details except the names of the vertices and the edges between them — we ensure that all our discoveries and methods can be used on graphs of any kind, regardless of what the graphs actually represent.  So, if we can find paths between vertices in graphs, it does not matter whether we are interested in finding paths in social networks or in molecules: the same method can be used in each case.  This is the power of abstraction.  By removing real-world details, our work becomes more useful because our methods can be applied in many different fields.

Each of the questions above has practical applications in diverse fields, as well as a rich theory.  For example, graph colouring started out in the nineteenth century with puzzles about colouring maps, but now has applications in timetabling, scheduling, computer science (in allocating variables in a computer program to memory registers inside the computer), and assigning radio frequencies to communications towers.  A good exercise is to think about how graph colouring can be used to model a problem of examination timetabling.