The Story of Louis Pósa
WOULD LIKE TO TELL YOU something of the life and works of a remarkable young Hungarian named Louis Pósa (pronounced pO.sha), who was born in the late 1940's. When quite young he attracted the attention of the eminent Hungarian mathematician Paul Erdös (pronounced air.dish), who did much to help him develop. Erdös has recently written and spoken about some of the child prodigies he has known and I would like to tell you his story of Pósa.
In case you are not familiar with Erdös, let me first tell you a little about him. He is now about 60 years old and he has been for many years an internationally known mathematician. His three great interests are combinatorics, number theory, and geometry. He is a problem solver rather than a theory builder, although a fair number of his more than 500 mathematical papers exceed 100 pages in length. For decades he has travelled the world's universities, seldom visiting anywhere for more than a few months. He spent the Fall term of 1970 at the University of Waterloo, and during this visit he told us about the Hungarian prodigies. Except for a few minor changes and additions, the following is his story of Pósa.
Erdös' Story. "I will talk about Pósa who is now 22 years old and the author of about 8 papers. I met him before he was 12 years oild. When I returned from the United States in the summer of 1959 I was told about a little boy whose mother was a mathematician and who knew quite a bit about high school mathematics. I was very interested and the next day I had lunch with him. While Pósa was eating his soup I asked him the following question: Prove that if you have n+1 positive integers less than or equal to 2n, some pair of them are relatively prime. It is quite easy to see that the claim is not true of just n such numbers, because no two of the n even numbers up to 2n are relatively prime.; Actually I discovered this simple result some years ago but it took me about ten minutes to find the really simple proof. Pósa sat there eating his soup and then after half a minute or so he said "If you have n+1 positive intergers less than or equal to 2n, some two of them will have to be consecutive and thus relatively prime." Needless to say, I was very much impressed, and I venture to class this on the same level as Gauss' summation of the positive integers up to 100 when he was just 7 years old."
At this point Erdös discussed a few problems in graph theory which he gave to Pósa. In order to avoid any misunderstandings, let us interject here a brief introduction to this material.
By a graph we do not mean anything connected with axes and coordinates. A graph consists of a collection of vertices (points) and a set of edges, each joining a pair of vertices. How the graph is pictured on paper is not essential. The edges may be drawn as straight lines or curves, and it is immaterial whether they are drawn so as to intersect or not. Points of intersection obtained by edges which cross do not count as vertices. Only the given vertices are the vertices of the graph. Also a graph need not contain every possible edge which could be drawn, that is, there are in general many different graphs with the same set of vertices.
A loop is an edge both of whose endpoints are the same vertex. Multiple edges occur when two or more edges join the same pair of vertices. In a general graph both loops and multiple edges are permitted. In a simple (or strict) graph neither loops nor multiple edges may occur. Throughout Erdös' story and the remainder of this essay the unmodified word graph is intended to mean simple graph. We continue now with the story.
"From that time onward I worked systematically with Pósa. I wrote to him of problems many times during my travels. While still 11 he proved the following theorem which I proposed to him: A graph with 2n vertices and n2 + 1 edges must contain a triangle. Actually this is a special case of a well-known theorem of Turán, which he worked out in 1940 in a Hungarian labor camp. I also gave him the following problem: Consider an infinite series whose nth term is the fraction with numerator 1 and denominator the lowest common multiple of the integers 1, 2, ...., n; prove that the sum is an irrational number. This is not very difficult, but it is certainly surprising that a 12 year old child could do it.
"When he was just 13, I explained to him Ramsey's theorem for the case k=2: Suppose you have a graph with an infinite number of vertices; there is either an infinite set of vertices every two of which are joined by an edge, or there is an infinite set of vertices no two of which are joined by an edge. (Incidentally, this theorem is the discovery of the late Frank Ramsey, a brother of the present Archbishop of Canterbury.) It took about 15 minutes for Pósa to understand it. Then he went home, thought about it all evening, and before going to sleep he had found a proof. "By the time Pósa was about 14 years old you could talk to him as a grown-up mathematician. It is interesting to note that he had some difficulty with calculus. He never liked geometry, and he never wanted to bother with anything that did not really excite him. At anything that did interest him, however, he was extremely good. Our first joint paper was written when he was 14 1/2. Pósa wrote several significant papers by himself, some of which still have a great deal of effect. His best known paper, on Hamiltonian circuits, for which he received international acclaim, he wrote when he was only 15!
"The first theorem that he discovered and proved by himself which was new mathematics was the following: A graph with n vertices (n = 4) and 2n - 3 edges must contain a circuit with a diagonal. This result is the best possible, because for every n, one can construct a graph with n vertices and 2n - 4 edges which fails to have a circuit with a diagonal.
"A problem which I had previously solved is the following: A graph with n vertices (n =6) and 3n-5 edges must contain two circuits which have no vertices in common. I told Pósa of the problem, and in a few days he had a very simple proof which was miles ahead of the complicated one I had come up with. A most remarkable thing for a child of 14.
"Pósa also found a beautiful proof that every graph with n vertices and n+ 4 edges contains two circuits which have no edges in common. (This also holds for general graphs.)
"I would like to make a few conjectures why there are so many child prodigies in Hungary. First of all there has been for at least 80 years a mathematical periodical for high-school students. Then there are many mathematical competitions. The Eötvöse-Kurshák competition goes back 75 years. After the first world war a new competition was begun for students just completing high school, and after the second war several new ones were started.
"A few years ago a different kind of competition was started. It is held on television. Bright high school students compete in doing questions in a given period of time. The questions are usually very ingenious and the solutions are judged by a panel of leading mathematicians such as Alexits, Turån, and Hajos. It seems many people watch these competitions with great interest even though they do not understand the problems.
"In Hungary a few years ago a special high school, the Michael Fazekas High School, was opened in Budapest for children who are gifted in mathematics. The school started just when Pósa was due to go to high school. He liked the school very much, so much so, in fact, that he refused to leave it for entrance into university two years early. Soon after attending Fazekas High School, Pósa was telling me of other boys in his class who he thought were better at elementary mathematics than he was. Among these boys was the now prominent Lovász."
It seems appropriate to complement the story of Pósa with a sample of his work. Accordingly, let us work through his beautiful proof of Dirac's theorem on Hamiltonian circuits.
Graphs have many interesting properties. In 1857 the Irish genius William Rowan Hamilton invented a game of travelling around the edges of a graph from vertex to vertex. Given a particular graph to begin with, the object of the game was to find a path in the graph which passes through each vertex exactly once.
Of course, in some graphs such a path does not exist. If, in addition to finding such a path, one can arrange to make the last vertex the same as the first, he obtains a Hamiltonian circuit, not just a Hamiltonian path. While a Hamiltonian circuit always provides a Hamiltonian path, upon the deletion of any edge, a Hamiltonian path may not lead to a Hamiltonian circuit (it depends on whether or not the first and last vertices of the path happen to be joined by an edge in the graph).
There are some necessary and some sufficient conditions known for the existence of a Hamiltonian circuit in a graph. For example, it is necessary to have as many edges as vertices, and it is sufficient to have all possible edges actually as vertices, and it is sufficient to have all possible edges actually in the graph. However, even in 1972 there are no known necessary and sufficient conditions.
In 1952 the European mathematician G.A. Dirac came up with the following simple sufficient condition. (The "degree" of a vertex is simply the number of edges that occur at the vertex.)
DIRAC's THEOREM. A graph with n vertices (n Ñ 3) in which each vertex has degree at least n/2 has a Hamiltonian circuit.
In 1962 Pósa produced the following proof. He proceeds indirectly. Suppose the given graph G which has n vertices and every degree at least n/2 is non-Hamiltonian, that is, does not possess a Hamiltonian circuit. We now proceed to a contradiction.
Firstly we embed G in a saturated non-Hamiltonian graph G' as follows:
Clearly not all possible edges occur in G or else it would be Hamiltonian already. Consider, then, the insertion of an edge which is missing from G.
If this insertion does not complete a Hamiltonian circuit then leave the edge in the graph. If it does complete a Hamiltonian circuit, take the edge back out. Go around G doing this at each missing edge. The order in which one tries the missing edges is unimportant. At the end of this tour, the resulting graph G' will still be non-Hamiltonian since no Hamiltonian circuit is ever allowed to remain intact, and yet it will be saturated in the sense that the addition now of any missing edge will be have to complete a Hamiltonian circuit (otherwise we would have left the edge in the graph when it was tried during our rounds).
Adding edges certainly does not diminish the degree of any vertex. Hence every vertex of G' has degree at least n/2.
Since G' is non-Hamiltonian, it cannot contain all possible edges. Suppose the edge between vertices v1 and vn is missing. Putting in this edge would complete a Hamiltonian circuit because G' is saturated. Thus, even without the edge v1vn, the graph G' must contain a Hamiltonian path from v1 to vn (inserting the edge v1vn merely completes this path into a circuit). Let us denote the order of the n vertices in this path by v1, v2, v3, ..., vn-1, vn.
Now if the vertex v1 happens to be joined to the vertex vi, we ask whether the vertex vn could possibly be joined to vi-1? The answer is "no." For, if vn were joined to vi-1, then G' would contain the Hamiltonian circuit
v1vivi+1 ... vnvi-1vi-2 ... v2v1.
This is impossible since G' is non-Hamiltonian.
While v1 is not joined to vn, we do know that v1 has degree at least n/2. Thus v1 is joined to at least n/2 vertices vi where i runs from 2 to n - 1. Consequently, there are at least n/2 vertices vi-1, where i - 1 ranges from 1 to n - 2, to which vn cannot possibly be joined. Since loops are not permitted, vn cannot be joined to itself, either. Altogether, then, there are more than n/2 vertices to which vn cannot be joined. This leaves fewer than n/2 vertices to which vn can be joined, contradicting the given fact that its degree is at least n/2. (QED)
We conclude with the statement of four recent theorems in the field of Hamiltonian circuits. The final one is the work of V. Chvátal, an energetic young Czech mathematician, who produced it during his stay at the University of Waterloo, where shortly before he had earned his Doctorate Degree.
DIRAC'S THEOREM (1952). A graph with n vertices (n=3) in which each vertex has degree at least n/2 has a Hamiltonian circuit.
ORE'S THEOREM (1960). If n=3 and, for every pair of vertices that are not joined by an edge, the sum of the degrees is at least n, then the graph is Hamiltonian.
PÓSA'S THEOREM (1962). Let G be a simple graph with n vertices. If for every k in 1= k (n - 1)/2, the number of vertices of degree not exceeding k is less than k, and if for n odd the number of vertices with degree not exceeding (n - 1)/2 does not exceed (n-1)/2, then G contains a Hamiltonian circuit.
CHAVTÁL'S THEOREM (1970). Let the graph G have vertices with degrees d1, d2, ..., dn, written in non-decreasing order. If for every i<n/2 we have either di = i + 1 or dn-1 = n-i, then the graph is Hamiltonian.
1. Find a Hamiltonian circuit in each of the following graphs:
2. Prove that there is no Hamiltonian circuit in each of the following graphs:
3. Prove there is no Hamiltonian path in either of the graphs:
4. Which of the following graphs have Hamiltonian circuits, and which have only Hamiltonian paths?
5. Six points in general position are given in three-dimensional space (that is, no 3 are collinear and no 4 are coplanar). The C (6,2) = 15 segments joining them in pairs are colored individually either red or blue at random. Prove that some triangle has all its sides the same color.
6. A set of moves in chess which takes a knight successively through all 64 squares is called a knight's tour. If the knight can go from the last square to the first one in one move, and thus go all around again, the tour is called re-entrant. A re-entrant knight's tour corresponds to a Hamiltonian circuit in a graph which has a vertex for each square and an edge joining the vertices representing squares X and Y if and only if a knight can go from X to Y in one move. Show that there is no re-entrant knight's tour on any chessboard which has dimensions 4 by n, n a natural number.
7. Model a proof of Ore's Theorem (above) after Pósa's proof of Dirac's Theorem.
8. Try your hand at proving some of the theorems Pósa worked through as a teenager. For example, prove that a graph with n vertices and n+4 edges contains two circuits with no edge in common. The proof of this is contained in the joint paper of Erdös and Pósa "On the Maximum Number of Disjoint Circuits of a Graph", Publications Mathematicae, Debrecen, 1962, 3-12, especially page 9. This journal may be listed under Kossuth Lajos Tudomanyegyetem, Mathematika Intezet.
9. Prove Ramsey's Theorem. If you have trouble, consult the following plan. Consider an infinite sequence of vertices, 1, 2, 3, ...
Suppose each pair is joined by an edge. The edge joining vertices n and n + p, p > 0, is considered to begin at n and end at n + p. Now all edges are colored either red or blue so that, for every vertex n, all the edges which begin at n have the same color. If all are red, then n is called a red vertex, etc. Which vertices are red and which blue is immaterial.
(a) Show in such a sequence there exists either an infinite set of vertices every two of which are joined by a red edge, or there exists an infinite set of vertices every two of which are joined by a blue edge. (Hint: Consider the set of red vertices and the set of blue vertices; at least one of these sets must be infinite.)
(b) Now complete the proof of Ramsey's theorem by showing that in every graph which has an infinite number of vertices one can determine a sequence of vertices as described above.
(Hint: Color all edges of the graph red. Then insert all the missing edges and color them blue. Take any vertex at all as vertex 1 of the sequence. Separate into classes R and B the vertices to which 1 is joined, respectively, by red and blue edges. At least one of R and B must contain an infinity of vertices. If both do, choose either. For definiteness, suppose R is infinite. Then take any vertex of R as vertex 2 of the sequence. Repeat the separation process with respect to vertex 2 and its infinite set B (forget all about set B). Choose any vertex of an infinite set thus obtained as vertex 3 of the sequence, and so on. From this sequence Ramsey's theorem is easily deduced by part (a). At the end rub out all the blue edges.)
10. Let A0, A1, A2, ..., A2n-1 denote, in cyclic order, the vertices of a regular 2n-gon. Let all the sides and diagonals be drawn to give graph G. Prove that every Hamiltonian circuit of G must contain two edges which are parallel lines in the diagram.
NOTE: This article appears as Chapter 2in Mathematical Gems (see below).
References and Further Reading
Behzad and Chartrand, Introduction to the Theory of Graphs, Allyn and Bacon, Boston, 1972.
F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.
R. Honsberger, Mathematical Gems, The Mathematical Association of America, 1973.