Nauru graph
| Nauru graph | |
|---|---|
 The Nauru graph is Hamiltonian. | |
| Vertices | 24 |
| Edges | 36 |
| Radius | 4 |
| Diameter | 4 |
| Girth | 6 |
| Automorphisms | 144 (S4×S3) |
| Chromatic number | 2 |
| Chromatic index | 3 |
| Book thickness | 3 |
| Queue number | 2 |
| Properties | Symmetric Cubic Hamiltonian Integral Cayley graph Bipartite |
| Table of graphs and parameters | |
In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.
It has chromatic number 2, chromatic index 3, diameter 4, radius 4 and girth 6. It is also a 3-vertex-connected and 3-edge-connected graph. It has book thickness 3 and queue number 2.
The Nauru graph requires at least eight crossings in any drawing of it in the plane. It is one of three non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these three graphs is the McGee graph, also known as the (3-7)-cage.