Is the collaboration graph of the second kind planar?
Our guess was that surely it was not, and we now have a proof. If we can find a homeomorphic copy of the complete graph on five vertices in C’, then we know that the graph cannot be imbedded in a plane. Here is one such copy we found by hand. We need five vertices, each of which is joined in C’ to each of the others, either by an edge or by a path, and all the paths have to be disjoint (none of the intermediate authors can occur more than once). The five vertices are Paul Erdös, Frank Harary, Ron Graham, Dan Kleitman, and Saharon Shelah. There are edges in C’ between Erdös and Graham, between Erdös and Kleitman, and between Erdös and Shelah. Although Erdös and Harary have two joint publications, each of those papers had a third author, so the Erdös-Harary edge is not in C’. There is a path in C’ from Erdös to Harary passing through Leo Moser, however. There is a path between Harary and Graham passing through Stefan Burr, a path from Harary to Kleitman passing through Jin Akiyama and No
