Of course, we hardly knew what the word planar meant, and we never breathed the qualification “complete bipartite graph”. Well, a graph is a sort of model, and the form it takes in this instance is a network: several shapes with lines connecting them. The specific graph that absorbed our time and attention featured three shapes resembling houses, and three big circles, one marked “G” for gas; the next “E” for electric; and finally one marked “W” for water, each representing a utility station. Each house needs all three services, so individual lines should connect each service with each house. The puzzle’s challenge is to draw these lines – nine in total – without having any line cross another.

Every graph with more than one connected shape is bipartite – that merely means that you can divide the shapes into two categories such that all connecting lines from the shapes in one category link with shapes in the other category. But a “complete” bipartite graph is one where all the lines are “filled in”: where each and every shape in one category is connected to every shape in the other.

Mathematicians like to use precise language whenever possible, so please note that the shapes connected are called VERTICES (singular, VERTEX) and the connecting lines are called EDGES. “Complete” graphs are given a special label: “K”, after the outstanding mathematician Kazimierz Kuratowski. If the “K” is followed by a single number, the graph is complete, with edges connecting each vertex to every other vertex. If the “K” is followed by two numbers separated by a comma, the graph is bipartite, with edges connecting each vertex in one category to every vertex in the other category. The “three houses” problem that occupied our time in youth is a K_3,3 model. If it could be drawn on a flat surface without edges crossing, it would be “planar” – but it can’t. Look at K₂ and K₃ in the diagram: it is easy to see that they are planar: no edges need to cross each other. But look K₄: at first stab, it seems that a pair of edges cross. However, a little ingenuity and a detoured edge demonstrate that K₄ can be drawn without crossing – so K₄ is planar. Unfortunately the complexity of K₅ makes it necessary to cross edges, so we can be sure that K₅ is non-planar.

The fact that K_3,3 and K₅ are both non-planar is important: Kuratowski demonstrated that any graph – whether complete or not – can be drawn in planar form (no edges crossing) UNLESS K_3,3 or K₅ (or both) are hidden inside them. It is obvious that K₅ is inside K₆, and K₇, and so on. Of complete graphs (not necessarily complete bipartite graphs, though), only K₂, K₃ and K₄ are planar. It’s much more fun trying to find K_3,3 or K₅ inside incomplete graphs. There are many activities here which deserve attention by programmers — and a fascinating new neighbourhood in the land of Mathematics. Consider these points...

 1.What mileage is there in thinking of K_3,3 and K₅ as “knots”, or “tangles” in a network?
 2. A graph can be represented by a simple array, made up of edges. For each edge there are two parameters: the vertices at each end. From such an array, consider how to discover the total number of vertices in the graph, and how they are connected. Can you devise a way to create the corresponding diagram? (Don’t worry about crossing edges).
 3. How can you find an embedded F₅ graph?
 4. How can you find an embedded F_3,3 graph?
 5. If you can answer these questions, you can write a program to establish whether or not a particular graph is planar.

An important thing to recognise about these types of Networks: in most circumstances, their characteristics are “plastic”. By this, mathematicians mean that you can move things around without disturbing the properties. In one diagram I have demonstrated that K₄ is planar, but it can still be drawn with two edges crossing – optionally. Whether or not it is drawn with edges crossing does not affect the fact that this particular graph is planar. Plasticity is a thing you see quite a lot in two mathematical disciplines: predicate logic (where truth, falsehood and implication are converted into “words” and manipulated by sentences) and topology (the study of relative shape and configuration). Networks are part of topology, but can be used as models for predicate logic. For example, flow of fluid through pipes, traffic through a city, and “critical path analysis”, so important to planning and time/motion studies. And how to allocate responsibilities by shoestring modelling.

Think of a pair of laced boots: the laces are subject to rules about bipartite graphs! The lacing pattern joins holes in two parallel rows: these holes form the vertices of a bipartite graph, with the lace itself making up the edges. There are an amazing number of different ways of lacing boots, some of them very effective for the purpose, whether they are in some respect symmetric or not. You may suppose that somebody in the dim corridors (or is it hallways?) of time has worked out which ways of lacing are most effective. You would probably be correct, but almost every day in some way, boot lacing becomes a brand new specific problem to solve. When it arises, it is called a “matchings” task.

You see, a Matching is a bipartite graph that has some edges connecting vertices from each side of an equal division. A “Maximum Matching” is when each vertex from one side has an edge that connects with a vertex from the other. A boot fully laced is an example of a “Maximum Matching”. (Actually, it is an example of TWO maximum Matchings, because each hole serves as a vertex to TWO edges: the lace coming in from under, and the lace coming out from over).

Matchings happen when you divide up the week’s leftovers for Saturday lunch: “you get the beef from Wednesday with the peas from Friday – I will have the macaroni from Thursday with the beets from Tuesday”. Matchings become problems when there are restrictions (“I don’t mind what I have, except I won’t have that macaroni”). Some years ago a workmate told me about a problem dumped on his schoolteacher wife: she was required to do a timetable that fully occupied the students yet employed the abilities of the teachers: Mr Dennis, for example, could teach Algebra and Science, but was a poor choice for English and Physical Education. I volunteered to look at the requirements of the problem and advise her on how to proceed. I instantly saw that the complexities boiled down to a Matchings problem (with a little bit more working out on the side) and knowing the algorithm, rattled off a full solution in spite of her own frustration.

The algorithm was a bit beyond her, but I am sure you will be able to master it. I did – and got a bottle as appreciation every autumn for a few years as I solved the problem with new parameters again.

The best way to run this Maximum Matchings algorithm is with a symmetric bipartite graph with at least some edges already entered. If nothing has been entered, you should make a few to start the whole thing off well. The best way to show you how is with an example.

Here’s a simplified version of the problem: There are five teachers and five subjects. teacher A can teach subjects 1, 3 and 4. Teacher B can teach 3 and 5. Teacher C is able to handle classes in 2 and 5. Teacher D is qualified for teaching 2, 4 and 5. Teacher E is qualified to teach 1 and 2. At one time, all five subjects are to be taught, so each teacher must be assigned one subject to teach at this particular time. On the basis of preferred choice, A has chosen to teach subject 1; B has chosen to teach subject 3; C has chosen 2 and D has chosen 4. This will not work, because the only unassigned teacher (E) does not teach the only unassigned subject (5). Something is going to have to change: how do we decide?

Step 1

Make up the diagram in the style of a bipartite graph: distinguish between ALLOWED edges and ASSIGNED edges. The allowed edges are in grey and the assigned in red.

Step 2

Label each of the unconnected vertices on the left part with an asterisk, and on the right mark all vertices that can be connected (but aren’t) with a starred vertex on the left. Mark them with the label of the particular starred vertex to which they potentially link.

Step 3

Taking in turn each newly-labelled vertex on the right, identify any assigned edge radiating from it, and label that edge’s left side vertex with the connecting vertex designation. In our example we consider vertices 1 and 2: 1 is already connected to vertex A and 2 is connected to C, so we write 1 alongside vertex A and 2 alongside vertex C.

Step 4

Consider the most recently labelled vertices in the left part, and follow all possible edges from them to vertices on the right which have no notation yet. In this case we consider vertices A and C: A links to unmarked vertices 3 and 4, and C links to unmarked vertex 5.

Step 5

Consider the most recently labelled vertices in the right part, and follow all possible edges from them to vertices on the left which have no notation yet: take already assigned edges in preference to other possibilities. In this case we consider vertices 3, 4 and 5: 3 already links to B and 5 links to D, as yet unmarked.

Step 6

Repeat steps 4 and 5 (marking vertices with possible connects, alternating left side and right side) every possible vertex has been noted. If any vertex remains, then unfortunately there is no “maximum matching” solution. In this case the vertices of the graph were all marked the first time through, so there is no change in step 6.

Step 7

Now go to the right side of the graph (numbered vertices) and find one that was not in the original assignment. In this case, the only such vertex is 5. Follow its notation back to the left side of the graph: and then THAT vertex’s notation back to the right, and so on until you can go no further. Vertex 5 links to C, then to 2, and from there to E and no further.

Step 8

Gather up the remaining vertices on the left that didn’t occur in the lacing in step 7, and match them up along edges already assigned: in this case these are A (linked to 1), B (linked to 3) and D (linked to 4).

The result is a complete matching using the edges built in step 7 and the edges connecting leftover vertices as in step 8.

We now have to resolve the linkage between the vertices in the lacing that occurred in step 7. Start on the left side with a vertex marked with an asterisk. In this case, it’s vertex E: so E teaches 2 and C is left to teach subject 5. The final result is: A teaches subject 1; B teaches subject 3; C teaches subject 5; D teaches subject 4; and finally E teaches subject 2.

The solution thus established may not be the only possible matching: but it is the optimum matching that pays regard to the restrictions and attempts to meet with initial requests (we only had to disappoint C, who had preferred subject 2).

A lot of complicated work, labelling vertices back and forth, you may think. But it isn’t really all that difficult. As you try it out a few times, you will not only get the hang of it – you will come to enjoy the challenge, and find yourself solving each new task as if it were a walnut and you were expert at getting all the nutmeat from its centre. As you do it a couple of times you will discover why and how it works.

With this little excursion through a curious region of Mathematics, you should have learned how to tell if a network has a knot in it somewhere, and how to solve problems matching one set to another – such as teachers and classes, children and toys, people available for committees and their responsibilities. And you have learned a lesson upon which we students wasted lots of time one summer: that you can’t get three different utilities to connect to more than two homes without pipes crossing somewhere.