A new proof of the Gauss interlace conjecture (Q1809518)

Let \(\Delta\) be a word over a finite alphabet \(E\); \(\Delta\) is a double occurrence word if each letter in \(E\) appears exactly twice. A Gauss code is a word corresponding to a closed curve in the plane, crossing itself in a finite number of points, each of which the curve passes through exactly twice; the letters are the crossing points. (Note that each Gauss code is a double occurrence word, but not conversely, as the word \(abcadcedbe\) illustrates: the corresponding graph is \(K_5\).) For each \(e\) in \(E\), let \(\Delta(e)\) be the set of letters from \(E\) occurring exactly once between two occurrences of \(e\). Two letters \(e\) and \(f\) of \(E\) are interlaced if \(f\) is in \(\Delta(e)\). The Gauss interlace conjecture is that Gauss codes, among the double occurrence words, can be characterized by properties of the interlace relation. Previously, \textit{P. Rosenstiehl} [C. R. Acad. Sci., Paris, Sér. A 283, 551-553 (1976; Zbl 0345.05130)] affirmed this conjecture. In the present paper he uses combinatorial maps to give a new proof.