The starfish graph is the 20-vertex, 30-edge cubic Hamiltonian graph illustrated above. It has girth 5, graph crossing number 4, graph diameter 4, and chromatic number 3.
A cubic graph is theta-connected if it has girth at least 5, every edge cut separating two subgraphs containing cycles has at least five edges, and every edge cut having at least seven vertices on each side has at least six edges (Robertson et al. 2019).
The starfish graph is the exceptional graph in the characterization of theta-connected graphs excluding the Petersen graph as a topological minor. Every such graph is an apex graph, is doublecross, or is isomorphic to the starfish graph. A theta-connected graph excluding the Petersen graph but containing the starfish graph as a topological minor must itself be isomorphic to the starfish graph (Robertson et al. 2019).
The starfish graph is implemented in the Wolfram Language as GraphData["StarfishGraph"].
