My computer tells me that there 195291625 graphs on 20 vertices with minimum degree at least 3 and maximum degree at most 6 and girth at least 5.

Sadly none of them have chromatic number 4, I just get 48 bipartite ones and the remainder being 3-chromatic.

Independent verification would be useful.

**Added** Here's a 21-vertex graph that is not the Brinkmann graph, but is 4-chromatic and has girth equal to 5, also in graph6 format for direct input to Sage. It has the same number of edges as a 4-regular graph but has two vertices of degree 3 and two of degree 5. I bet that it is obtained from the Brinkmann graph by some small edge-swap move.

```
g = Graph("T???C@?K@OA_A_b?AWAQ_?kPCGc`OFCG?da?")
Graph 1, order 21.
0 : 7 13 18 19;
1 : 8 15 17 19;
2 : 9 10 19 20;
3 : 9 11 14 18;
4 : 10 12 13 15;
5 : 11 13 17 20;
6 : 12 14 16 19;
7 : 0 14 15 20;
8 : 1 16 18 20;
9 : 2 3 15 16;
10 : 2 4 17 18;
11 : 3 5 19;
12 : 4 6 20;
13 : 0 4 5 16;
14 : 3 6 7 17;
15 : 1 4 7 9;
16 : 6 8 9 13;
17 : 1 5 10 14;
18 : 0 3 8 10;
19 : 0 1 2 6 11;
20 : 2 5 7 8 12;
```

**More added**

There are smaller 4-chromatic girth-5 graphs than Brinkmann's graph, because some of the examples that are appearing have fewer *edges* even though they have the same number of vertices. The search is about 10% complete and there are 7 graphs found so far.

The prettiest one has just 40 edges and an automorphism group of order 5 consisting of a single fixed point and 4 5-cycles (which is vaguely reminiscent of Mycielski's construction).

**Final Addition**

After a little over 31 hours on the same multi-core machine, the computation of the full list of graphs with minimum degree at least 3, maximum degree at most 6 and girth at least 5 terminated.

Of the 5006797077 graphs constructed, just 18 had chromatic number 4 and therefore have an equal claim to being the smallest 4-chromatic graphs of girth 5 (at least in terms of counting vertices).

Among these graphs, 1 has 40 edges, 3 have 41, 12 have 42 and 2 have 43 edges. One is the 4-regular Brinkmann graph. The automorphism groups have orders 14 (Brinkmann graph), 5 (the element of order 5 has one fixed point and 4 x 5-cycles), 2 (8 times) and 1 (8 times). Some of the graphs are obtained from the others by adding/deleting an edge, but mostly not.

For those interested, the graphs (in graph6 format) are as follows:

```
T???C@?K@OA_A_b?AWAQ_?kPCGc`OFCG?da?
T???C@?GC_B?@_p?@W@cADS@`CCDg@HP@GY?
T???C@?GC_B?@_p??T@cAOp?Po@Y@AOsA_e?
T???C@?GC_B?@_p??T@cAAE_SoAEgD@K?l?_
T???C@?GC_B?@_p??T@cAAE_So@Q@AEGA_e?
T???C@?GC_B?@_p??T@cAAE_So@Q@AEgA_e?
T???C@?GC_B?@_b?@WAIGCWaac?HpBOS@QP?
T????A?OD?B?P_[?Ac@W?@F?I`@BKAQPAROO
T????A?O@?Q?F?S_HC@S?HGQGWFAC?b__FK_
T???C@?g?o?os?PCKP?d_AoOpCCPG@WC?Dg?
T???C@?G?oA_A__`IGB?QH?jK?C`c@RG?FW?
T???C@?GC_@_E_QOOS?M?CX?s@_PobCWBCQ?
T????A?O@_@_g_Y?BC?H_CD_R@QDWCQo@DA_
T???C@?G?_P?R?IOOa?i?SDAqAACR?T__ck?
T????A?O@?Q?R?[?BO@P?AF?E`?bSAEGadO_
T????A?O@?Q?R?[?BO@P?AF?E`GbSAEGadO_
T????A?WA_D?@_`CGSCc?@J?JH?pcEAK?t?_
T???C@?GC_H?@_T??[BCOAIac_CSa@aK?C[_
```

10more comments