Given the nets of 4 cubes with the faces coloured in 4 colours, build a tower so that on each vertical wall no colour is repeated, that is all 4 colours appear.
A connected graph is a graph in which we can get from any vertex to any other by travelling along the edges. A tree is a connected graph with no closed circuits (or loops. Prove that every tree has exactly one more vertex than it has edges.
Label the joints and legs of these graph theory caterpillars so that the vertex sums are all equal.
Published July 2004,August 2004,February 2011.
A graph is a mathematical object made up of points (sometimes called nodes, see below) with lines joining some or all of the points. You can think of the world wide web as a graph. The points and lines are called vertices and edges just like the vertices and edges of polyhedra. Here is a graph representing a cube.
Graph Theory is a whole mathematical subject in its own right, many books and papers are written on it and it is still an active research area with new discoveries still being made. Graphs are very useful in designing, representing and planning the use of networks (for example airline routes, electricity and water supply networks, delivery routes for goods, postal services etc.) Graphs are also
used to solve problems in coding, telecommunications and parallel programming.
In some of these applications the actual distances and the geometrical shape of the graph is not important, simply which vertices in the system are linked, and these applications come into the branch of maths known as topology. In other applications distances between the vertices, the direction of flow and the capacity of the 'pipes' are significant. Rather confusingly there are two different
languages used by mathematicians. In this article we use the graph theory language.
You can trace a path in the graph by taking a pencil, starting at one of the vertices and drawing some of the edges of the graph without lifting your pencil off the paper. A path is simply a sequence of vertices where each vertex is connected by a line to the next one in the sequence. A circuit is any path in the graph which begins and ends at the same vertex.