Smallest nonhamiltonian 2-connected bicubic graph with chromatic index 3
I found this rather trivial example for a bicubic nonhamiltonian 2-connected graph with chromatic index 3:
$\hskip0.5in$
Is this the smallest one? If not can you construct a smaller one?
Your example is the smallest.
I take it "bicubic" means bipartite and 3-regular. In a bipartite graph, the edge-chromatic number (or chromatic index) is equal to the maximum degree, so every bicubic graph has chromatic index 3.
There are data files of various families of graphs available. Cubic graphs (apparently meaning connected 3-regular simple graphs) up to 22 vertices are available on Gordon Royle's website, in a format which can be imported into Mathematica.
I ran a command like
LG = Import[
"http://school.maths.uwa.edu.au/~gordon/remote/cubics/cub20.g6"];
for each data file size (04 up to 20), then ran
Select[LG, (ConnectedGraphQ[#] && ! HamiltonianGraphQ[#] &&
Min[VertexDegree[#]] == 3 && Max[VertexDegree[#]] == 3 &&
BipartiteGraphQ[#]) &]
to find any nonhamiltonian bipartite ones. (The conditions for connectivity and vertex degree should be redundant, since only connected 3-regular graphs are included in the data.) None exist with fewer than 20 vertices. Moreover, only the one example exists with 20 vertices. Mathematica presents it like this (I have checked that it is isomorphic to yours):