It is known that the smallest 4-chromatic graph of girth 4 is the [Grötzsch graph](http://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph) (11 vertices). What happens for girth 5?


The [Brinkmann graph](http://en.wikipedia.org/wiki/Brinkmann_graph) (21 vertices) has chromatic number 4, girth 5 and is 4-regular. Moreover it is the smallest graph (in terms of the order) with these three properties.


Dropping the 4-regularity constraint, is there a graph of smaller order than the Brinkmann graph that is 4-chromatic and of girth 5? I haven't found anything in the literature but I may have missed it.



What is the smallest 4-chromatic graph of girth 5?
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[_

```

