How I solved an Erdös Problem

In the last issue of Zimaths, personal encounters with Paul Erdös were described by `one of the lucky many' who had the chance to meet `Uncle Paul' on various occasions. This time the same person wants to report on how he and another chap solved one of Erdös' problems. And, like many of Erdös' problems, it had a prize attached to it --- US$100. A prize which --- for the problem solver(s) -- would mean even more than a travel grant of US$1000 for participation in a conference, say.

For the money came by a cheque signed by Paul Erdös; and once the cheque was cashed it would be sent back to the problem solver(s) upon request. Almost like a ritual, many a recipient of such a cheque would then frame it, and hang it up on the wall of their office or study. It was like a diploma or a medal of a special kind. Now, to tell the story...

Once upon a time (1990, actually) there was a conference in Hindsgavl in Denmark, quite close to the town of Odense where the poet Hans Christian Andersen, writer of the now famous childrens' stories (but originally meant for adults), had once lived. The conference was not on childrens' stories however, but on graph theory and combinatorics. I had the honour to chair Uncle Paul's talk and the subsequent problem seminar --- believe me, it is on videotape, although not for my sake, but for Uncle Paul's (naturally). The first problem Erdös spoke about was this, albeit in a different phrasing:

Suppose an n x n matrix is given, where entries are integers such that no integer appears more than once in the same row, and any two rows have at most one element in common. Prove that one can rearrange the entries in each row in such a way that equal entries always appear in the same column. The first example below gives you a clue how to proceed, the second shows that it may not be possible if even one pair of rows has two elements in common.

The prize attached to that problem was and still is US$500. Try it before you go to bed and have nice dreams. Hopefully it won't create a headache or nightmares for you. For me it did, since I had started working on that problem in 1975; at that time its prize was $50. So, apart from trivial partial solutions of this problem, my only contribution to Erdös problems was that my (and others') futile attempts to solve this one jacked up the prize of the problem tenfold. ``This was not entirely due to inflation,'' Erdos asserted in his talk.

The next problem he stated was the Cycle-Plus-Triangles Problem which can be stated as follows: Suppose you are given a regular 3n-gon (eg for n=2, we would have a hexagon) C in the plane and n triangles whose sides are diagonals of C such that every vertex of C belongs to exactly one of these n triangles. Show that the vertices of C can be coloured with colours r,b,y such that no two vertices of the same colour are adjacent in C (ie, are joined by an edge of C), nor do they belong to the same triangle.

Stated in graph theoretic terms this problem reads: Every 4-regular graph decomposable into a Hamiltonian cycle and n disjoint triangles (thus having altogether 3n vertices) has a vertex colouring with 3 colours. The prize attached to this problem: US$100.

As time went by (actually, roughly 14 months later) I was invited to spend two weeks at the Technical University in Ilmenau, Germany, just to have a good time with my colleagues -- mathematically. There was also my younger colleague Michael Stiebitz. He had had the nerve to fiddle around with this US$100 problem, and dared to invite me (the ``burned child'' --- see above) to discuss it seriously. ``Poor soul,'' I thought, ``If you think I'll ever try again to seriously tackle an Erdös problem, you are badly mistaken.'' However I couldn't resist jointly fiddling around. He had come up with some preliminary results (some of which contained easily correctible flaws) and a yet-to-be-proved theorem stating that in a graph G decomposable into a Hamiltonian cycle H and n>0 disjoint triangles whose edges are diagonals of H, the number of Eulerian orientations of G (or, equivalently, the number of arc subsets of an Eulerian orientation D of G, inducing Eulerian subdigraphs --- the empty set had to be counted as well) is 2 mod 4.

As he explained easily to me, this theorem, if true, would imply the validity of Erdös' conjecture. But how to prove it? He thought induction on the number n of triangles might do, the induction beginning with n=0 in which case we're safe since a cycle has just two (Eulerian) orientations. BIG DEAL! He had also the idea of absorbing the edges of a triangle into the Hamiltonian cycle H by splitting the three vertices of the triangle appropriately. ``Sounds nice'' I thought, ``but what then?'' In any case, I didn't take his ideas too seriously --- not because they seemed inappropriate, but because of yet unknown complications, difficulties, etc., which I believed to be in store for us.

I had arrived in Ilmenau on a Sunday evening; by Wednesday midnight (or was it 1am, Thursday?) I had a counterexample to Erdös' conjecture. However, by 8:30am the next morning, while waiting for Michael in the Department so I could show him the counterexample, it turned out, upon checking it again, that it was indeed NOT a counterexample. The only thing I had proved was that brain cells of certain people work with a varying degree of accuracy depending on the time of day.

By 10:00 am, Michael had arrived and we went to a classroom to summarize what we'd got so far and discuss how to split the three vertices of a triangle in order to apply induction. This was my job and it was quite easily done. Then we found some identities between numbers of certain arc sets inducing Eulerian subdigraphs (Eulerian arc sets, for short) in the given Eulerian orientation D of the graph G, and Eulerian arc sets in the graphs having only n-1 triangles resulting either from the above splitting operation or by simply deleting one of the triangles (Without loss of generality, we could assume that in D, the Hamiltonian cycle was oriented counterclockwise, while the triangles were oriented clockwise).

In any case, we ended up with a sum of six terms, each being an integer, and such that the terms could be grouped into three pairs of equal numbers; that is, we had a sum of the form 2(a₁+a₂+a₃). We stared at it. ``What shall we do with it? What should it be?'' I had the idea to go back to the sum of six terms and write each term as a sum of two smaller terms (which we succeeded in doing in a very appropriate way) and ended up with a sum of twelve terms. Using the identities we had found before, we were able to group these terms into three quadruples of equal numbers; ie we had a sum of the form 4(b<sub>1</sub>+b<sub>2</sub>+b<sub>3</sub>), ie a sum = 0 mod 4. ``We have proved it!'' Michael exclaimed. I stared at him without really knowing what we had proved. ``The theorem is true!'' (ie this sum being = 0 mod 4 supposedly proved the original claim of his theorem; to be precise, we had another sum already in store -- of this sum we knew that it was = 2 mod 4 by induction). It took him a few minutes to make me see why this sum of 12 terms being = 0 mod 4 implied the original claim, ie the number stated in the theorem, being = 2 mod 4. He was deliriously happy --- I was not.

``Listen, my young friend, you don't prove a conjecture by Paul Erdös within a few hours (by that time it was approximately 4pm, and we had had lunch). ``And we did it!'' ``I don't believe it --- let's go through it from the beginning!'' We did; no mistake found. However, I insisted that there must be a flaw somewhere. He refuted my suspicions. In order not to quarrel too much over a possibly false proof, I offered a compromise: ``Let's go and have dinner, then we come back, erase everything that's on the blackboard, and start from scratch.'' He agreed. Said, done, and it was 10pm, but I was still not convinced. Another compromise: ``Let's have a coffee, and then we go through it again. If we don't find a mistake, then I'll believe it'', I said (I had to prop up my low blood pressure anyway).

Michael and I went to the Secretary's Office and he made the coffee for me, since we could hardly expect to find a secretary at that time of day. I sipped my coffee, taking my time and wiggling my head in disbelief, while Michael seemed quite satisfied even without coffee. ``Let's go back to the classroom and do it again,'' I said, putting my empty cup on the tray. ``If you want to, go there alone,''he said, ``I'm going home 'cause I'm tired.'' I refused to disillusion myself without his presence, so we both left. He accompanied me to my room on campus, and about 30 minutes later I had fallen asleep in my bed, still having doubts about the correctness of our proof.

At 9.00 am next morning (Friday) I found the handwritten draft of our joint paper waiting in the Secretary's office for me! Later on that day, Michael went to see his mother in Berlin over the weekend, and then on to Denmark. The second week of my stay in Ilmenau I spent without him, but enjoying a relaxed atmosphere with other colleagues.

A few months later we received our cheques (US$50 for each of us), after the paper got accepted for publication, and I did what others did with their cheques --- cashed it and framed it. Here is a photograph of it.