This is the McGee graph. It is 3-regular graph, meaning that every vertex has 3 neighbors. It also has girth 7, meaning that the shortest cycles have length 7. What makes the McGee graph special is that it has the least number of vertices of any 3-regular graph of girth 7.
This picture by Greg Egan shows a hypercube with all vertices except the bottom labelled by duads, that is, 2-element subsets of a 6-element set. There are 15 duads, while the hypercube has 16 vertices.
Notices of the AMS · Bulletin of the AMS
American Mathematical Society · 201 Charles Street Providence, Rhode Island 02904-2213 · 401-455-4000 or 800-321-4267
© Copyright , American Mathematical Society · Privacy Statement