Graph Theory Uncovers the Roots of Perfection

The following is a version of an article by Dana Mackenzie that appears in Science 297 (5 July 2002), 38. This article was written before the proof of the strong perfect graph conjecture (SPGC) was published. It appears in Maria Chudnovsky, Neil Robertson, Paul D Seymour and Robin Thomas, 'The strong perfect graph theorem', Annals of Mathematics (2) 164 (1) (2006), 51-229. For this paper the four authors were awarded the 2009 Delbert Ray Fulkerson Prize.

For more details of this award, see THIS LINK.

Graph Theory Uncovers the Roots of Perfection.

A newly minted proof tells how to recognise which arrangements of points and lines are the crème de la crème

To some, perfection is priceless. But for four graph theorists, it has a very specific value. If their solution to one of the oldest problems in their discipline - a classification of so-called perfect graphs - holds up, they will reap a $10,000 bounty.

The strong perfect graph conjecture (SPGC) has perplexed mathematicians for more than 40 years. "It's a problem that everyone in graph theory knows about, and some people in related areas, particularly linear programming," says Paul Seymour of Princeton University, who announced the proof at a meeting of the Canadian Mathematical Society last month. Its solution might enable mathematicians to quickly identify perfect graphs, which have proper ties that make otherwise intractable problems involving networks easy to solve.

The graphs in question consist of nothing more than dots and lines. Each line connects exactly two dots, or nodes. The SPGC grew out of mathematicians' fascination with colouring graphs in such a way that no two nodes of the same colour are connected, a problem rooted in the real-world business of colouring maps. When Wolfgang Haken and Kenneth Appel proved the famous Four-Colour Theorem for planar maps in 1976, they did it by means of graph theory.

Colouring problems make sense for other kinds of graphs as well. In a cell-phone network, for example, the nodes are transmitters, the lines connect any two transmitters whose ranges overlap, and the colours correspond to channels. Colouring the net-work amounts to assigning channels so that no adjacent transmitters broadcast on the same channel. Of course, the phone company would want to use the smallest possible number of channels, which is called the chromatic number

\chi

of the network.

It's easy to see that any group of nodes that are all connected to one another must all be different colours. Graph theorists call such a dense web of nodes a clique. Thus, in any graph, chi has to be at least as large as the size of the biggest clique, a number known as

\omega

. In a perfect graph, in fact,

\chi

and

\omega

are exactly equal. More than that, they stay equal no matter how many nodes you knock out of the graph, as long as the remaining nodes keep their links intact. A cellphone network based on a perfect graph could run with optimum efficiency even if some of its transmitters were knocked out (although it would cover less area).

A perfect graph is like a perfect chocolate cake: It might be easy to describe, but it's hard to produce a recipe. In 1960, however, Claude Berge, a mathematician at the Centre National de la Recherche Scientifique in Paris, did just that. He noticed that every imperfect graph he could find contained either an "odd hole" or an "odd anti-hole." An odd hole is a ring of an odd number (at least 5) of nodes, each linked to its two neighbours but not to any other node in the ring. An anti-hole is the reverse: Each node is connected to every other node in the ring except its neighbours.

Berge boldly conjectured that any graph that avoided these two flaws (such graphs were later named "Berge graphs") would be perfect. But he couldn't prove it, and his speculation became the SPGC. At the same time, Berge also ventured a less definitive pronouncement known as the "weak" perfect graph conjecture.

Seymour, along with co-authors G Neil Robertson of Ohio State University in Columbus and Robin Thomas of the Georgia Institute of Technology in Atlanta, began working on the SPGC in 2000. They were motivated in part by a grant from the privately funded American Institute of Mathematics in Palo Alto, California, which promotes work on high-profile unsolved problems. Although mathematicians have identified a dizzying variety of perfect graphs - 96 types at last count - the three researchers focused on just two types, called bipartite graphs and line graphs, as well as their anti-graphs. Following a strategy suggested by another perfect-graph aficionado, Gerard Cornuejols of Carnegie Mellon University in Pittsburgh, Pennsylvania, they proved that any Berge graph that is not one of these types can be decomposed into smaller pieces that are.

Cornuejols had done more than just suggest a strategy. He put his money where his mouth is, offering $5000 for the proof of a particular step that had eluded him, as well as $5000 for completing the proof of the full SPGC. To collect the prize, Seymour and his collaborators will have to get their work published, which might take a year or more while other graph theorists scrutinise a proof that will likely run to 150 or 200 pages.

The early betting is that they will collect the prize. "I don't know the details of the proof, but I trust that it is basically correct," says László Lovász of Microsoft Research, who proved the weak perfect graph theorem in 1972. "In the first version of a complicated and long proof like this, there are always some gaps and, at the same time, often substantial possibilities for simplification. But I do know the general plan, and I have no doubt that it is now working." Late last month, Seymour and his student Maria Chudnovsky presented more details at a workshop in Oberwolfach, Germany. András Sebő of the Institut d'Informatique et Mathématiques Appliquées in Grenoble, France, who co-organised the workshop, says the excellent track record of the authors, and the ease with which Seymour and Chudnovsky fielded all questions, leaves "not much doubt" that the proof will hold up.

Before the workshop, Seymour e-mailed news of the proof to Berge, who proposed the problem. He later heard that Berge, who is seriously ill, had the message read to him in the hospital. "He was happy," Seymour says.

Dana Mackenzie

Dana Mackenzie is a writer in Santa Cruz, California.

Last Updated December 2025