Smallest nonhamiltonian 3-connected graph with chromatic index 3 The Barnette-Bosák-Lederberg Graph is  the smallest known example of a planar 3-connected nonhamiltonian graph, i.e., the smallest known counterexample to Tait's Hamiltonian graph conjecture.
What is the smallest one when you drop the planarity condition, but keep the condition that the chromatic index is 3?
 A: My previous answer was not the smallest: The (11,2)-generalized Petersen graph, with 22 vertices, is the smallest example present in Mathematica's GraphData database, but there is an example on 20 vertices not included in the database.
It is infeasible to generate every graph smaller than 22 vertices to see if there's a smaller example than the one present in GraphData. However, I eventually realized that 3-connected graphs with chromatic index 3 must be 3-regular (aka cubic, aka trivalent),
because vertex-connectivity $\kappa \leq \delta$ (minimum degree) $\leq \Delta$ (maximum degree) $\leq \chi'$ (chromatic index). And Gordon Royle's website has files with all 3-connected cubic graphs with up to 20 vertices (scroll down to "3-connected cubic graphs".)
I imported all these into Mathematica to identify the nonhamiltonian graphs, of which there are 986. Unfortunately, Mathematica is not able to reliably compute the chromatic index of graphs; there is a function EdgeChromaticNumber in the package Combinatorica, but it doesn't work properly for graphs converted from Mathematica's built-in Graph type. So I exported the 986 3-connected nonhamiltonian cubic graphs to Sage, which found that exactly one of them has chromatic index 3. (The rest are all, perforce, class 2.)

Mathematica and Sage independently confirm that it's nonhamiltonian, 3-connected, and has chromatic index 3. It is also nonplanar.
The graph6 string for this graph (which can be easily imported to various programs, including Mathematica and Sage) is "SsP@P?WC_G__?W?O?@??I?@??AG?BO?@g".

The smallest example with chromatic number 3 (as opposed to chromatic index) is called 7-graph 344, with 7 vertices and 13 edges (the chromatic index is 5).
