What is the graph on the cover of "Graph Theory" by Bondy & Murty?

270 Views Asked by At

This is a pretty light question, but does anyone recognize the graph on the cover of the Springer GTM "Graph Theory" by Bondy & Murty? Here is the picture of the graph:

enter image description here

1) Does this graph have a special name?

2) What sort of counter-example does it serve?

3) Why are some vertices "filled in" and some of them blank? Maybe I know this one: This is probably explaining the concept of the dual graph where the faces become new vertices, and the two faces are adjacent if they share an edge in the original graph.

By the way, I don't have a copy of the book, so it is possible that authors mention the cover page somewhere in the book. Note that similar questions have been asked in the past. For example, see this MSE post.

2

There are 2 best solutions below

1
On BEST ANSWER

It is two graphs, the one in black has $10$ vertices and is 3-regular so by the laws of graph theory examples it is the Petersen graph.

The one in grey is the dual graph, which is the complete graph $K_6$.

The missing information is that this drawing is not an embedding on the plane, but on the projective plane. This can be “realised” as a disk where the each boundary point is identified with the one diametrically opposite.

This drawing shows six white vertices on the boundary, but really this is only three vertices - the north-east vertex and the south-west vertex are actually the same vertex.

0
On

This graph (at least the light vertices) looks like the (9,3) configuration graph shown in the upper-left corner of the table here: http://mathworld.wolfram.com/NonahedralGraph.html

I note that it's planar, polyhedral, and has threefold symmetry—and suspect it was chosen for these properties because they're aesthetically pleasing.