NOTE: This transcription was contributed by Martin P.M. van der Burgt, who has devised a process for producing transcripts automatically. Although its markup is incomplete, we believe it serves a useful purpose by virtue of its searchability and its accessibility to text-reading software. It will be replaced by a fully marked-up version when time permits. —HR
A not so simple theorem about undirected graphs. See pg.2.
(The other day Alain Martin told me that C.S.Scholten had shown him a rather complicated proof for what seemed a fairly simple theorem, and commucated the theorem to me. I felt challenged and tried to find a “simple” proof myself. The proof that I found is recorded below, partly because I think my proof simple enough to have some beauty, partly because perhaps the theorem is not so simple after all: it took me a full day to prove it and another five hours to write the following in manuscript.)
In a finite, undirected graph we call two nodes that are directly connected by an edge of the graph each other’s “neighbours”. Let P and Q be two different nodes of the graph. We define a “path from P to Q ” as a sequence of nodes, starting with P and ending with Q , such that no node occurs more than once in it and any two adjacent nodes in the sequence are each other’s neighbours in the graph. Of such a path, P and Q are called “the terminal nodes”, the ones in between are called “the internal nodes”. (If P and Q are not each other’s neighbours, a path from P to Q has at least one internal node.)
The theorem states that for any pair of different nodes A and B that are not each other’s neighbours, there exists a node C that is an internal node of any path from A to B , or there exists a pair of paths from A to B that have no internal node in common.
In order to prove it, we arbitrarily select one path from A to B and call it “the special path”; its edges are called “the special edges”, its internal nodes are called “the special nodes”. For brevity’s sake we denote on the special path the direction from A to B as the direction “from left to right”.
Next, let P and Q be two non-adjacent nodes of the special path: we define “an external path between P and Q ” as a path between P and Q of which no node of the special path is an internal node. If between a P and a Q of the special path an external path exists, we call the special nodes between P and Q —if P is to the left of Q : the special nodes that are to the right of P and also to the left of Q— “covered” by that external path.
It is clear that a covered special node can never be a candidate for C an external path allows a path from A to B that bypasses all special nodes it covers.
There are now two mutually exclusive cases: either there exist one or more special nodes not covered b an external ath or each special node is covered by at least one external path.
In the first case the theorem is true, for each path from A to B must pass through all uncovered special nodes, hence any special node that is not covered by any external path can be taken as node C.
In the second case the theorem is also true, for if each special node is covered by at least one external path, two paths from A to B exist that have no internal node in common. We shall show this existence by construction.
We shall construct a sequence of external paths PQ_{0}, PQ_{1}, ... , PQ_{N} . The left-hand terminal node of the path PQ_{i} will be denoted by P_{i} ; the right-hand terminal node of the path PQ_{i} will be denoted by Q_{i} . Denoting the relation “to the left of” by “<” our sequence of external paths shall have the following two properties:
Property 1:
A = P_{0} < P_{1} < Q_{0} ≤ P_{2} < Q_{1} ≤ P_{3} < Q_{2} ≤ ..... Q_{N-2} ≤ P_{N} < Q_{N-1} < Q_{N} = B . |
For i ≠ j the external paths PQ_{i} and PQ_{j} have no internal node in common . |
Because (see property 1) we have for 0 < i < N
P_{i} < Q_{i-1} ≤ P_{i+1} < Q_{i} , |
For PQ_{0} we choose an external path with P_{0} = A —because the leftmost special node is covered, such an external path exists— and Q_{0} as far to the right as possible. If Q_{0} coincides with B the construction stops here, otherwise we proceed repeatedly as follows until an external path PQ_{N} with Q_{N} = B has been selected.
Let PQ_{i} be the last external path selected and let Q_{i} not coincide with B . Then Q_{i} is a special node and, hence, covered by at least one external path. For PQ_{i+1} we choose a path covering Q_{i} with Q_{i+1} as far to the right as possible. For i = 0 , the fact that Q_{0} < Q_{1} and the way in which PQ_{0} has been selected imply P_{0} < P_{1} ; for i > 0 , the fact Q_{i} < Q_{i+1} and the way in which PQ_{i} has been selected imply that the path PQ_{i+1} does not cover Q_{i+1} and hence we conclude Q_{i-1} < P_{i+1}, The quality P_{i+1} < Q_{i} follows from the fact that PQ_{i+1} covers Q_{i} . This proves the inequalities mentioned in property 1 . Property 2 follows from the fact that PQ_{i+1} has no internal node in common with PQ_{k} for 0 ≤ k ≤ i : such a common node would provide an external path between Pk and Qi+1 , the existence of which is not compatible with the construction of Q_{k} as a rightmost node. And this completes our proof.
Acknowledgements. I am indebted to C.S.Scholten for having found the theorem, to Alain Martin for having screened my proof, and to my mother, mrs.B.C.Dijkstra - Kluyver for having discovered a serious omission in my proof’s first presentation —as a matter of fact, the omission was so serious that she did not believe the proof— .
Note. With directed paths A → B and P ⇒ Q the proof can be applied directly to the more interesting case of directed graphs.
Plataanstraat 5 | prof.dr.Edsger W.Dijkstra |
5671 AL NUENEN i | Burroughs Research Fellow |
The Netherlands | . |
Transcribed by Martin P.M. van der Burgt
Last revision