{'fraction_non_alphanumeric': 0.050365411151428424, 'fraction_numerical': 0.04022077988449941, 'mean_word_length': 3.4305445488509, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graphs with girth at least 5 with orders between 20 and 32

We prove properties of extremal graphs of girth 5 and order 20<=v<= 32. In each case we identify the possible minimum and maximum degrees, and in some cases prove the existence of (non-trivial) embedded stars. These proofs allow for tractable search for and identification of all non isomorphic cases.


Introduction
In this paper we consider graphs of girth at least 5, i.e. graphs which have no 3-cycles or 4-cycles. In [9], the maximum number of edges in graphs of girth at least 5 with v vertices, f 4 (v), were established for v ≤ 30, and v = 50, and the number of unique (up to isomorphism) graphs with f 4 (v) edges, F 4 (v), was caculated for v ≤ 21 and v = 50. Note that, once f 4 (v) has been established, it is straightforward to generate F 4 (v) for n < 20 using nauty's geng tool [12].In [7] and [8] we introduce two symmetry breaking constraints for combinatorial search and illustrated their effectiveness by applying it to the problem of finding graphs with girth at least 5 (and other combinatorial problems). We were able to reproduce the results of [9] and find values F 4 (v) that were previously unpublished. Our symmetry breaking constraints alone were not sufficient to crack some of the harder cases. We were however able to reduce our search space by applying new theoretical results for cases v > 22. In many cases we were able to identify non-trivial embedded stars that must be present in a graph with the maximum number of edges and girth at least 5, and fixing this embedded star made our search tractable. An outline of the proof of the existence of such stars is given in [8], but for space reasons did not include full proofs. We give the full proofs in this paper. All of the graphs for F 4 (v), where 20 ≤ v ≤ 32 are presented as incidence arrays in our appendices and a full list in graph6 notation (as implemented in nauty [12]) can be obtained by contacting the authors directly.

Preliminary Definitions and Results
In this section we give some preliminary definitions and results that will be useful in this paper.
The girth of a graph Γ = (V, E) is the size of the smallest cycle contained in it. Let F k (v) denote the set of graphs with v vertices and girth at least k+1. Let f k (v) denote the maximum number of edges in a graph in F k (v). A graph in F k (v) with f k (v) edges is called extremal. The number of non-isomorphic extremal graphs in F k (v) is denoted F k (v). Extremal graph problems involve discovering values of f k (v) and F k (v) and finding witnesses. In [2] the authors attribute the discovery of values f 4 (v) for v ≤ 24 to [9] and for 25 ≤ v ≤ 30 to [10]. In [9] the authors report values of F 4 (v) for v ≤ 21. In [9] and [15] algorithms are applied to compute lower bounds on f 4 (v) for 31 ≤ v ≤ 200. Some of these lower bounds are improved in [1] and improved upper bounds for 33 ≤ v ≤ 42 are proved in [4]. Values of f 4 (v) for v ≤ 30, and of F 4 (v) for v ≤ 21 are available as sequences A006856 and A159847 of the On-Line Encyclopedia of Integer Sequences [13]. We have extended sequence A159847 to include values for 22 ≤ v ≤ 32, following the results presented in this paper.
In the remainder of this paper, as we are only interested in graphs with girth at least 5, we abbreviate f 4 (v) and F 4 (v) to f (v) and F (v) respectively.
Lemma 1 If Γ is an extremal graph of order v, with e = f (v) edges, whose minimum and maximum degrees are δ and ∆ respectively, then Values of f (v) for 22 ≤ v ≤ 30 can be found in [9], and those for v = 31 and v = 32 are given in [7]. By applying Lemma 1, and observing (by counting edges) that δ = ∆ is only possible when v∆ = 2f (v) we obtain possible values of (δ, ∆), for 22 ≤ v ≤ 33. These are given in Table 1 Definition 2 If Γ is a graph of girth at least 5 we say that Γ has a embedded S D,[d 0 −1,d 1 −1,...,d D−1 −1] star if Γ has a vertex of degree D whose children have degrees at least d 0 , d 1 , . . . , d D−1 respectively.
Note that the children and grandchildren of a vertex in a a graph of girth at least 5 are distinct, and there are no edges between the children. If Γ is such a graph and has minimum and maximum degrees δ and ∆, then any vertex x of degree ∆ is the centre of a trivial embedded S ∆,[δ−1,δ−1,...,δ−1] star. In order to reduce the number of isomorphic graphs produced, any combinatorial search for extremal graphs will assume a fixed position of such a star (for example, with central node as vertex 0). The purpose of this paper is to show that in some cases an extremal graph must contain larger (non-trivial) embedded stars, in some cases containing all of the vertices in the graph. This allows us to fix such a star and reduce both our search space and the number of isomorphic graphs generated.
Definition 3 A node x of an extremal graph is said to be a sink node if it has maximum degree and is the centre of an embedded star that contains all of the vertices (i.e. x is at distance at most 2 from all other vertices).
From a result in [9], no two vertices in an extremal graph of girth at least 5 are at distance greater than 3 from each other. Theorem 1 For each 20 ≤ v ≤ 32, an extremal graph Γ must have (δ, ∆) taking one of the pairs of values indicated in Table 2. In each case, we show the number of edges (f (v)), the largest star known to be embedded in Γ, the number of distinct graphs (F (v)), and the method of proof. In all cases Lemma 3 is employed. The "method" column indicates whether the graphs were obtained from [9] (G) or, if not, whether search is employed (based on the proven existence of embedded stars) (S), and whether some (or all) graphs are constructed by hand (H). Note that S, H denotes that some of the graphs were found using search, and some by hand.
Definition 5 A linear space Λ on a set of n points V is a collection B = {B 1 , . . . , B b } of subsets of V called blocks, such that every block has at least two points and each pair of points is in exactly one block. A prelinear space Λ is a set of blocks on V in which every block has at least two points and each pair of points is in at most one block.
Any prelinear space can be extended to a linear space, by adding suitable blocks of size 2, so we tend to use the term linear space and prelinear space interchangeably. A linear space with no blocks of size 2 is called a proper linear space. Proof No pair of elements in V \ V 1 can appear in more than one set b i as Γ contains no 4-cycles, so B is a (pre) linear space. Similarly, no set b i contains two vertices that are adjacent in Γ, as Γ contains no 3-cycles.
Note that in the context of linear spaces, we generally refer to the elements of the blocks as points, whereas in the context of graphs the elements of edges are vertices. When applying Lemma 4 this distinction is less clear.
Definition 6 A (v, k, 1)-packing design is a linear space on a set V where the blocks all have size k. For any v, k function P (k, v) is called the maximum packing number of k and v, and is the maximum number of blocks in such a packing design.
The following result follows from a simple counting argument (see [11]): Lemma 5 For any k ≤ v, The upper bound is not achievable in some cases. Absolute values for P (k, v) for 3 ≤ k ≤ 6 and 1 ≤ v ≤ 28 are given in Table 3. These are obtained from [14], [6], and theoretical results in [5].
The following Lemma is a direct consequence of the definition of P (k, v): No linear space on v points contains more than P (k, v) blocks of size k.
Proof (i) Any point p in b with regularity reg p intersects r p − 1 other blocks, and no other block contains more than one element of b, so b intersects Σ p∈b reg p − 1 other blocks, and the result follows. (ii) If we sum the weights of the blocks, for every vertex p, reg p is counted reg p times. So Σ b∈B wt(b) = Σ p (reg 2 p ). For every i > 0 there are deg i vertices of regularity i, so Σ b∈B wt(b) = Σ i>0 deg i .i 2 , as required. Proof There are no points of regularity greater than 3 (or the blocks containing such a point would contain 13 distinct points), and at most 4 of regularity less than 3 (if there are 5, then 22 spaces must be filled by 7 points, implying at least one point of regularity greater than 3). Suppose that there are two non-intersecting blocks, then they must each have weight at most 10 and each contain a pair of vertices of regularity at most 2 (from Lemma 7). It follows that (deg 2 , deg 3 ) = (4,8). But then two of the blocks contain only points of regularity 3 and have weight 12 which contradicts Lemma 7.
Lemma 9 If Λ is a linear space on 13 points with 9 blocks of size 4, then (1) there is no set of 3 non-intersecting blocks. (2) There are at most 3 pairs of non-intersecting blocks.
Proof First observe that if there is a set of 3 parallel blocks or more than 1 pair of parallel blocks then no point is in at most 1 block, or removing the point leaves a linear space on at most 12 points with 8 blocks of size at least 4 with a non-intersecting pair of blocks. There is no linear space on fewer than 12 points with 8 blocks of size at least 4 [3], and if v = 12 we have a contradiction to Lemma 8. So every point is in between 2 and 4 blocks and (deg 2 , deg 3 , deg 4 ) = (3, 10, 0), (4,8,1), (5,6,2) or (6,4,3). By Lemma 7 no block can have weight more than 12 and Σ b∈B wt(b) = 4deg 2 +9deg 3 +16deg 4 .
(1) If there is a set of 3 non-intersecting blocks, then there are 3 blocks of weight at most 10, and so Σ b∈B wt(b) ≤ 102. This is only possible if (deg 2 , deg 3 , deg 4 ) = (3, 10, 0). But the set of 3 parallel blocks must each contain two of the vertices of degree 2, and so must intersect, which is a contradiction. (2) If there are 4 pairs of non-intersecting blocks then there are 8 blocks with weight at most 11 and Σ b∈B wt(b) ≤ 100, which is impossible.
Proof No point can be in 4 blocks. If p has regularity 3 then for every block containing p there is a point of regularity 1 (as all blocks have weight at most 10, by Lemma 7). So we must solve the following set of equations/inequalities: deg 1 + 2deg 2 + 3deg 3 = 30; deg 1 + deg 2 + deg 3 ≤ 16, and deg 1 ≥ 3deg 3 . There are 3 solutions, giving the result required.
In the remainder of this paper we present all extremal graphs of orders 20 ≤ v ≤ 32. In all cases, for all graphs Γ we provide the adjacency matrix, degree sequence, edge set, relevant sets S Γ,n , and any other relevant material one of the appendices (A-M) to this paper.
Proof There is precisely one graph on 20 vertices with 41 edges. This is stated in [9] and the graph is given in [10]. This graph is given in Figure 1 (the numbering of the vertices is our own). There are 3 embedded S 5, [3,3,3,3,2] stars. Note that the sink nodes corresponding to these stars are precisely the vertices of degree 5, namely 0, 1 and 2.

Lemma 11
If Γ is a graph of girth at least 5 on 20 vertices with 41 edges, then (deg 3 , deg 4 , deg 5 ) = (1,16,3) and every element of S Γ,3 contains 2 vertices of degree 4 and a child of a sink node, namely the single vertex of degree 3. This graph is given in Figure 1, and is represented as an embedded star with sink node 0 in Figure 2. Note that
Suppose that there is a vertex of degree 3, x say. Since δ = f (21) − f (20), by Lemma 3, Γ can be constructed from the extremal graph on 20 vertices described in Lemma 11, Γ , by adding a vertex x of degree 3 and edges from x to all vertices in an element of S Γ ,3 . Since no element of S Γ ,3 contains vertices of degree 5, it follows that ∆ = 5. So we have (δ, ∆) = (3,5  by Lemma 11 every element of S Γ ,3 contains single vertex of Γ of degree 3 that is a child of every sink node, it follows that every sink node of Γ is a sink node of Γ of degree 5 whose children all have degree 4. Hence there is an embedded S 5, [3,3,3,3,3] star. If (δ, ∆) = (4, 5) then any node x of degree 5 must only have children of degree 4 and the result follows.

Lemma 12
If Γ is a graph on 21 vertices of girth at least 5 with 44 edges, then one of the following holds: (i) (deg 3 , deg 4 , deg 5 ) = (1,15,5) and Γ has 3 embedded S 5, [3,3,3,3,3] stars and is isomorphic to the graph shown in Figure  3. In this case every element of S Γ,3 contains 3 vertices of degree less than 5, and the child of a root of degree 4. (ii) (deg 3 , deg 4 , deg 5 ) = (0, 17, 4), all vertices of degree 5 are sink nodes and Γ is isomorphic to one of the graphs shown in Figure 4. In both cases S Γ,3 is empty.
Proof From the proof of Theorem 3, (δ, ∆) = (3,5) or (4,5). If (δ, ∆) = (3, 5) then (deg 3 , deg 4 , deg 5 ) = (1,15,5) and Γ is obtained from the extremal graph Γ on 20 vertices shown in Figure 1, by adding an additional vertex x and edges from x to one of the sets S Γ ,3 identified in the proof of Lemma 11. Using nauty [12], it can be shown that all graphs constructed in this way are isomorphic to the graph shown in Figure 3 (note that in the figure (and in Figure  4) neighbours of leaf nodes are indicated as sets). In this case the sink nodes are 0, 1 and 2 and S Γ,3 = {{4, 9, 20}, {5, 12, 20}, (8, 13, 20}, {17, 18, 19}}. The result follows. Suppose then that there is no vertex of degree 3. Then (δ, ∆) = (4, 5) and (deg 4 , deg 5 ) = (17, 4). All vertices of degree 5 are sink nodes. By [9], we know that there are 3 extremal graphs (21, 44), so there are two graphs of this type. They must be isomorphic to the two graphs shown in Figure  4, which have been shown to be non-isomorphic. Note that graph (b) can be obtained from graph (a) by replacing edge (8,20) with edge (11,20) and in graph (a), the 3 grandchildren of degree 5 have the same parent, and in graph (b) two of the grandchildren of degree 5 have the same parent, and the other does not. In both cases S Γ,3 is empty.
If there is a vertex, x, of degree 3, then since δ = f (22) − f (21), by Lemma 3, Γ can be constructed from one of the extremal graphs on 21 vertices described in Lemma 12, Γ , by adding a vertex x of degree 3 and edges from x to all vertices in an element of S Γ ,3 . Since S Γ ,3 is non-empty, it follows that Γ is the first graph defined in Lemma 12, which has a sink node of degree 5 with 4 children of degree 4. Since every element of S Γ ,3 only contains elements of degree less than 5, it follows that, in Γ, ∆ = 5. So (δ, ∆) = (3,5). Since every element of S Γ ,3 contains a child of a sink node of Γ of degree 4, Γ has an embedded S 5, [4,3,3,3,3] star.
Suppose then that there are no vertices of degree 3. Thus (δ, ∆) = (4, 5) and there are 16 vertices of degree 4 and 6 of degree 5.
If there are no sink vertices, all vertices of degree 5 have 5 neighbours of degree 4 (and 20 grandchildren), and it follows from Lemma 4 that there is a linear space on the vertices of degree 4. This linear space consists of 6 blocks of size 5. Let B denote this set of blocks and Γ 4 the graph formed by the vertices of degree 4 and the edges between them. It follows from Lemma 10 that, since any vertex in V 4 that is in i blocks in B has degree 4 − i in Γ 4 , if deg i is the number of vertices of degree i in Γ 4 , (deg 1 , deg 2 , deg 3 , deg 4 ) = (1, 12, 3, 0), (0, 15, 0, 1) or (0, 14, 2, 0). If, in Γ 4 , there is a chain of 4 vertices of degree 2, a − b − c − d say, then no two of a, b, c can be in the same block of B, or there is a cycle of length at most 4. Hence two of the blocks of B contain a, two contain b and two contain c. Now similarly d is not in a block in B with b or c, so must be in both blocks of B containing a, which is not possible. So we assume there is no such chain and it follows that (deg 1 , deg 2 , deg 3 , deg 4 ) = (0, 15, 0, 1). By a similar argument, if a is a vertex of degree 1 then there is no chain a − b − c where b and c have degree 2. Hence, if (deg 1 , deg 2 , deg 3 , deg 4 ) = (1, 12, 3, 0) and a the vertex of degree 1, with neighbour b, eitherb has degree 3, or b has degree 2 and its other neighbour c has degree 3. In either case, there is a vertex of regularity 1 in the blocks that is in no block with a, hence one of the blocks on a contains no vertex of regularity 1 which is not possible (see the proof of Lemma 10).
So (deg 1 , deg 2 , deg 3 , deg 4 ) = (0, 14, 2, 0). Let x and y be the vertices of degree 3. Since there can be no component consisting entirely of vertices of degree 2 (or it would either contain a cycle of length 3, or a chain of at least 4 vertices of degree 2) either x and y are in different components, or Γ 4 consists of a single component. If x and y are in different components of Γ 4 then their components contain a single vertex of odd degree and all other vertices of even degree, which is not possible (the sum of the degrees in a component must be even). So Γ 4 consists of a single component and either there is a single path (of length at most 4) from x to y and cycles containing x and y respectively, or 3 paths from x and y, together containing all of the vertices of degree 2. In either case, there is a chain of at least 4 vertices of degree 2.
These graphs are shown in Figures 5-7. In each case the graph is drawn as a star about a sink node with 4 children of degree 4 and one of degree 5.   The vertices adjacent to each of the grandchildren is indicated as a set. Examination of these graphs using a computer reveals that in each case every element of S Γ,3 contains no vertex of degree greater than 4, and contains at least one vertex that is the child of a sink node. See Appendix C for details.

Lemma 14
If Γ is a graph of girth at least 5 on 22 vertices with 47 edges then S Γ,3 contains at most 4 non-intersecting sets. If all vertices of degree 3 (if any) are contained in a single element of S Γ,3 then Γ is Γ 1 or Γ 2 of Lemma 13. If in addition there are two vertices of degree 4 which have fewer than 3 − deg 3 neighbours of degree 4 between them, Γ is Γ 2 . In this case there are three vertices of degree 4 which have fewer than two neighbours of degree 4 and they each have one such neighbour, p, q and r respectively. No two of p, q and r are in a common element of S Γ,3 with the vertex of degree 3.
Proof From examination of the graphs in Appendix C, S Γ,3 has at most 4 non-intersecting sets and if S Γ,3 contains a set X of 3 non-intersecting sets then Γ is graph Γ 0 or Γ 2 . Examination of the vertices of degree 4 shows that all vertices of degree 4 have at least two neighbours of degree 4 unless Γ is   Γ 2 and the vertex is 1, 16, or 17, which have neighbours of degree 4: 12, 13 and 9 respectively. No two of these vertices are in an element of S Γ,3 with the vertex of degree 3 (i.e. vertex 0).
If there is a vertex, x, of degree 3, then since δ = f (23) − f (22), by Lemma 3, Γ can be constructed from one of the extremal graph on 22 vertices described in Lemma 13, Γ , by adding a vertex x of degree 3 and edges from x to all vertices in an element of S Γ ,3 .
Since in each case S Γ ,3 contains no vertex of degree greater than 4, (by Lemma 13), in Γ ∆ = 5. Hence (δ, ∆) = (3,5). In addition, since S Γ ,3 contains a child of a sink node of Γ , it follows that Γ has a sink node of degree 5 with 2 children of degree 5 and 3 of degree 4.
If there is no vertex of degree 3 then (δ, ∆) = (4, 5) and (deg 4 , deg 5 ) = (15,8). If no vertex of degree 5 has any neighbour of degree 5 then there is a linear space on 15 points with 8 blocks of size 5, contradicting Lemma 6. Since every vertex of degree 5 has at least one neighbour of degree 5, the result follows.
Lemma 16 Suppose that Γ is a graph of girth at least 5 on 23 vertices with (δ, ∆) = (4, 5) and Γ 4 = (V 4 , E 4 ) the subgraph of Γ on the vertices of degree 4, then there is at most one vertex in V 4 that is in no edges in E 4 . If two vertices have degrees 0 and 1 in V 4 , then they have a common neighbour of degree 5 in Γ.
Proof From the proof of Lemma 15 there are two such graphs with (δ, ∆) = (4,5). Only the first of these contains a vertex of degree 4 that has no neighbours of degree 4, (vertex a say). There are two vertices that have degree 1, and each of these are in an edge in Γ with a. See Appendix D for details.
Proof From Table 1 we know that in this case all vertices have degree 4 or 5. There are 12 vertices of degree 4 and 12 vertices of degree 5. Since δ = f (24) − f (23), by Lemma 3, Γ can be constructed from one of the extremal graph on 23 vertices described in Lemma 15, Γ , by adding a vertex x of degree 4 and edges from x to all vertices in an element of S Γ ,4 . In all cases, S Γ ,4 includes precisely one child of degree 4 of any central node of an embedded S 5, [4,4,3,3,3] star. It follows that Γ contains an embedded S 5, [4,4,4,3,3] star.
Lemma 17 (1) There is 1 graph Γ of girth at least 5 on 24 vertices with 54 edges. Proof(1) By Theorem 6 (δ, ∆) = (4, 5) and there is an embedded S 5, [4,4,4,3,3] star. Restricting search to this case produced a set of graphs. Isomorph elimination using nauty [12] revealed there to be one such graph, with 2 sink nodes. This is shown in Figure 8 as a star about vertex 13, together with set S Γ,3 . Clearly all elements of S Γ,3 contain only vertices of degree 4. (2) and (3) follow from observation, see Appendix E for details.
Proof We know from Table 1 that in this case the possible values for (δ, ∆) are (3,5), (3,6), (3,7), (3,8), (4,5) and (4,6). If there is a vertex, x, of degree 3, then since δ = f (25) − f (24), by Lemma 3, Γ can be constructed from the extremal graph on 24 vertices described in Lemma 17, Γ , by adding a vertex x of degree 3 and edges from x to all vertices in an element of S Γ ,3 . Since S Γ ,3 only contains vertices of degree 4, it follows that (δ, ∆) = (3,5). Since Γ contains a star [5, [4, 4, 4, 3, 3]), Γ does too, and the result for δ = 3 holds. If (δ, ∆) = (4, 5) then (deg 4 , deg 5 ) = (11,14) and the sets of vertices of degree 4 adjacent to each vertex of degree 5 form a linear space (see Lemma  If no vertex of degree 5 has more than 2 neighbours of degree 5 then Λ consists of 14 blocks of size at least 3. It follows from [3] that Λ has at least 11 blocks of size 3 (and, correspondingly, at least 11 vertices of degree 5 have two neighbours of degree 5. Let x be such a vertex of degree 5. Let S be the embedded S 5, [4,4,3,3,3] star with x as root (see Figure 9). Note that A and B denote the sets of children of the two children of x of degree 5, and R the set consisting of the remaining grandchildren of x, and the vertices p 1 and p 2 that are not contained in the star. Since we have assumed that all vertices of degree 5 have at most one child of degree 5, A and B contain at most 1 vertex each of degree 5 and R contains at least 9 vertices of degree 5 and at most 2 of degree 4. Now if A contains a vertex of degree 5 then it must have at least 2 neighbours in R that do not have degree 5. So R contains exactly 9 vertices of degree 5 and 2 of degree 4. Then B must contain a vertex of degree 5, which must be adjacent to the same two elements of R, and there is a square. It follows that A and B contain no vertices of degree 5, and every element of R has degree 5. But then p 1 must be adjacent to 3 elements of A ∪ B (as it can have at most 2 neighbours of degree 5), which is impossible, as there will then be  Figure 9: 25, embedded S 5, [4,4,3,3,3] star a square. So there is at least one vertex of degree 5 that has more than 2 neighbours of degree 5 and so Γ either has an embedded S 5, [4,4,4,4,3] star, or has no embedded S 5, [4,4,4,4,3] star but has an embedded S 5, [4,4,4,3,3] star.
Proof Restricting our search to graphs with values of (δ, ∆), with the identified embedded stars from Theorem 7 produced a set of graphs. Isomorph elimination using nauty [12] revealed there to be six graphs, A 0 , . . . , A 5 . Using a computer the graphs were shown to satisfy the stated properties. For details see Appendix F.

Lemma 19
If Γ is a graph of girth at least 5 on 25 vertices with 57 edges and X 1 , X 2 , X 3 parallel elements of of S Γ,3 then 1. if (δ, ∆) = (4, 5) one of the sets must contain a vertex of degree 5 2. it is not possible that X 1 contains all vertices of degree 3 and there are no edges between X 1 and X 2 , or between X 1 and X 3 .
Proof Follows from examination of graphs Γ 0 . . . Γ 5 (and corresponding sets S Γ,3 ) as shown in Appendix F.
In the other, S Γ,4 contains 1 set, which consists of 4 vertices of degree 4, none of which is a child of a sink node. In one graph there is a unique set X = {X 1 , X 2 } containing two non-intersecting elements of S Γ,3 that each consist of elements of degree 4, and, for all In the other graph there is no such set X.
Proof From Theorem 8 all extremal graphs on 26 vertices can be constructed by adding a new vertex x, and edges to a set of 4 vertices that is a set in S Γ ,4 , where Γ is one of the 6 extremal graphs on 25 vertices. This produced a set of 6 graphs. Isomorph elimination using nauty [12] revealed there to be two distinct graphs, A 0 , A 1 . Using a computer the graphs were shown to satisfy the stated properties. See Appendix G for details.
Proof We know from Table 1 that in this case the possible values for (δ, ∆) are (4,5) and (4,6). Since in all cases δ = f (27) − f (26), by Lemma 3, Γ can be constructed from an extremal graph on 26 vertices described in Lemma 20, Γ , by adding a vertex x of degree 4 and edges from x to all vertices in an element of S Γ ,4 . By Lemma 20 it follows that, in Γ, (δ, ∆) = (4, 5) and (since any non-empty set S Γ ,4 does not contain the child of a sink node), Γ has an embedded S 5, [4,4,4,4,4] star.
Proof From Theorem 9 all extremal graphs on 27 vertices can be constructed by adding a new vertex x, and edges to a set of 4 vertices that is a set in S Γ ,4 , where Γ is one of the 2 extremal graphs on 26 vertices. Since, by Lemma 20 only one of the extremal graphs on 26 vertices has a non-empty set S Γ ,4 , and this contains only one set, this produces a single graph. Using a computer the graph was shown to satisfy the stated properties. See Appendix H for details.
If (δ, ∆) = (4, 5) then (deg 4 , deg 5 ) = (4,24) and there are at most 16 edges from the vertices of degree 4 to the vertices of degree 5. Hence at least one vertex of degree 5 has no neighbours of degree 4 and the result follows.
If (δ, ∆) = (4, 6) then, since deg 4 > 0 and deg A vertex of degree 6 can have at most one neighbour of degree 6, and so has at least 5 edges to the set S containing the vertices of degrees 4 and 5. It follows that there is a linear space on deg 4 + deg 5 points containing at least deg 6 blocks of size 5. It follows from Lemma 6 that this does not hold when i ≥ 14.
If there is no embedded S 6, [4,4,4,3,3,3] star then every vertex of size 6 has at least 4 neighbours of degree 4. This is only possible if there is a linear space on deg 4 points that has at least deg 6 blocks of size at least 4. By Lemma 6, this does not hold if 5 < deg 4 ≤ 11. So there is an embedded S 6, [4,4,4,3,3,3] star except possibly where deg 4 = 5, 12 or 13.
Suppose that deg 4 = 5 then (deg 4 , deg 5 , deg 6 ) = (5, 22, 1). If there is no embedded S 6, [4,4,4,3,3,3] star the vertex x of degree 6 is adjacent to at least 4 of the vertices of degree 4. There are 3 cases to consider: x is adjacent to 5 vertices of degree 4 and 1 of degree 5; x is adjacent to 4 vertices of degree 4 and there is a further edge among the vertices of degree 4; and x is adjacent to 4 vertices of degree 4 and there is no further edge among the vertices of degree 4. In all cases, let T denote the set of edges from the vertices of degree 5 to the vertices of degree 4 and 6. In the first two cases, |T | = 16 and it follows that the graph Γ 5 on the 22 vertices of degree 5 has 47 edges and is extremal.
In the first case, each of the vertices of degree 4 are in edges with 3 of the vertices of degree 5. Since all of the vertices of degree 4 are adjacent to x, it follows that S Γ 5 ,3 contains 5 non-intersecting sets. This is not possible by Lemma 14.
In the second case, let Γ 5 be one of the extremal graphs Γ 0 , Γ 1 , Γ 2 described in Lemma 13. Let x be the vertex of degree 6 and {a, b, c, d, e} the vertices of degree 5, where x is adjacent to a, b, c and d, and d and e are adjacent. Let A, B, C, D, E and X be the sets of vertices in V 5 that are adjacent to a, b, c, d, e and x in Γ. Note that each of these sets contain vertices that have degree at most 4 in Γ 5 , |A| = |B| = |C| = |E| = 3, and |D| = |X| = 2. Sets |A|, |B|, |C|, |D| and |X| do not intersect, and any element that is in two of the sets is in E. It follows that E contains all of the vertices of degree 3 in Γ 5 and all of the vertices of degree 4 in Γ 5 are in precisely one of the sets. Set X must contain 2 elements of degree 4, p and q say, that are not in edges with any element in sets A, B, C or D (or there is a square). So any neighbour of degree 4 of p or q must be in set E, with the vertex of degree 3 in Γ 5 , and p and q have at most 2 neighbours of degree 4 between them. By Lemma 14 this is not possible.
If x is adjacent to 4 vertices of degree 4 and there is no further edge among the vertices of degree 4, then let Σ = {a, b, c, d} denote the set of vertices of degree 4 adjacent to x, e the remaining vertex of degree 4, and X the set of two vertices of degree 5 that are adjacent to x. Let Γ 5,e denote the graph formed by removing x ∪ Σ . Then Γ 5,e has 23 vertices and 50 edges, is extremal and has vertices of degree 4 or 5. The vertices that have degree 4 in Γ 5,e are those that are in an edge in Γ with an element of Σ, vertices in X and e. By an argument similar to the above, the elements of X must have at most 1 neighbour (i.e. e) of degree 4 In Γ 5,e . But Lemma 16 the elements of X have a common neighbour in Γ 5,e . Since, in Γ, both elements of X are adjacent to x, there is a cycle of length 4. This is a contradiction, so if (deg 4 , deg 5 , deg 6 ) = (5, 22, 1) there is an embedded S 6, [4,4,4,3,3,3] star.
Suppose that (deg 4 , deg 5 , deg 6 ) = (12,8,8). If there is no embedded S 6, [4,4,4,3,3,3] star every vertex of degree 6 is adjacent to at least 4 vertices of degree 4. So there is a linear space on 12 points containing 8 blocks of size at least 4. It follows from [3] that there must be 12 blocks of size exactly 4. There is one such linear space, and all of the blocks intersect, by Lemma 8. It follows that no two vertices of degree 6 can be adjacent to each other, or adjacent to a common vertex of degree 5. Since every vertex is adjacent to two vertices of degree 5 this is impossible. So if (deg 4 , deg 5 , deg 6 ) = (12,8,8) there is an embedded S 6, [4,4,4,3,3,3] star.
Suppose that (deg 4 , deg 5 , deg 6 ) = (13,6,9). If there is no embedded [4,4,4,3,3,3] star every vertex of degree 6 is adjacent to at least 4 vertices of degree 4. So there is a linear space Λ on 13 points containing 9 blocks of size at least 4. Since there is no linear space on 13 points with a block of size 5 and 8 blocks of size at least 4, there are exactly 36 edges from the vertices of degree 6 to the vertices of degree 4. By Lemma 9, Λ has no set of 3 non-intersecting blocks so no vertex of degree 6 has two neighbours of degree 6, and so is in at least one edge with a vertex of degree 5. Hence there are at least 9 edges from the vertices of degree 6 to the vertices of degree 5. If a vertex of degree 5 is in two edges with vertices of degree 6, the corresponding blocks in Λ must not intersect (or there is a square). By Lemma 9, Λ has at most 3 pairs of non-intersecting blocks and it follows that there are exactly 9 edges from the vertices of degree 6 to the vertices of degree 5, and every vertex of degree 6 is in one edge with another vertex of degree 6. This is not possible (the sum of the degrees in the graph on the vertices of degree 6 must be even).

Lemma 22
There are 4 graphs of girth at least 5 on 28 vertices with 68 edges.
Proof (1) From Theorem 10 all extremal graphs on 28 vertices with δ = 3 can be constructed by adding a new vertex x, and edges to a set of 3 vertices that is a set in S Γ ,3 , where Γ is the extremal graph on 27 vertices. Since, by Lemma 21 there is one graph Γ and 5 sets S Γ ,3 , there are 5 graphs to check. Using nauty it was shown that all of these graphs are isomorphic, so there is only one graph in this case. Using a computer the graph was shown to satisfy the stated property.
If e = 2 then the graph on the vertices of degree 5 (Γ ) has 54 edges and is extremal. If x is a vertex in Γ of degree 4 that is in no edges with other vertices of degree 4, then the graph on the vertices of degree 5 and x has 25 vertices and 58 edges, which is not possible. So there are two parallel edges on the vertices of degree 4. The sets of vertices of degree 5 adjacent to each of the vertices of degree 4 must not intersect (as Γ contains no vertex of degree less than 4) and for each pair of adjacent vertices of degree 4 there is no edge between their neighbours of degree 5 (or there is a square). It follows that S Γ ,3 contains 4 non-intersecting elements for which there are are two pairs with no edge between either of the pairs. This is not possible by Lemma 17.
If e = 0 then restricting search to this case showed there to be no graphs. The search in this case took 13 hours.
If e = 1 then suppose that v 1 and v 2 are adjacent. The graph Γ with vertices V \ {v 1 , v 2 } has 26 vertices and 61 edges, so is maximal. The sets of three vertices of degree 5 adjacent to v 1 and v 2 respectively must be distinct and there must be no edge between these sets. So S Γ ,3 contains a pair of nonintersecting sets that have no edges between them. By Lemma 20 there is one maximal graph Γ for which S Γ ,3 contains such a pair, and one suitable pair ((X 1 , X 2 ) say). Hence, since Γ is constructed from Γ by adding a new pair of adjacent vertices v 1 and v 2 with edges to the vertices in X 1 and X 2 , there is one graph Γ.
(3) Let Γ be a graph with (δ, ∆) = (4, 6). By the proof of Theorem 10 If there is an edge between two vertices, v 1 and v 2 of degree 4, then removing the vertices and all edges on them leaves an extremal graph on 26 vertices. Since neither extremal graph on 26 vertices has any vertices of degree 6, it follows that the sets of vertices adjacent to v 1 (that are not v 2 ) and to v 2 (that are not v 1 ) are elements of S Γ ,3 that are parallel, have no edges between them, and contain at least one vertex of degree 5. Only one of the extremal graphs on 26 vertices have such a pair of sets, and there are 3 such pairs. These lead to two non-isomorphic extremal graphs Γ which have (deg 4 , deg 5 , deg 6 ) = (6, 20, 2) and (deg 4 , deg 5 , deg 6 ) = (7, 18, 3) respectively.
Let us assume then that there are no edges amongst the vertices of degree 4. If a vertex v 1 of degree 5 has 2 neighbours, q 1 , q 2 say, of degree 4, then removing v 1 , q 1 and q 2 leaves an extremal graph on 25 vertices (with 57 edges), Γ say. Let X 1 , X 2 and X 3 be the remaining neighbours of v 1 , q 1 and q 2 in Γ. Then X 1 , X 2 and X 3 are parallel elements of S Γ ,3 for which there are no edges between X 1 and X 2 , or between X 1 and X 3 . In addition, since Γ has no vertices of degree 3, any vertex of degree 3 in Γ must be in X 1 , X 2 or X 3 . Since there are no edges between vertices of degree 4 in Γ, if follows that all of the vertices of degree 3 in Γ are in X 1 . There is no suitable extremal graph Γ , by Lemma 19. So in Γ no vertex of degree 5 has more than 1 neighbour of degree 4.
Consider the embedded S 6, [4,4,4,3,3,3] star, with root p. Three of its children have degree 4 and all other vertices of degree 4 must be grandchildren, with parents having degree 5 (as there are no edges between vertices of degree 4). No two of these grandchildren can have the same parent (as no vertex of degree 5 has more than one child of degree 4). It follows that i ≤ 6.
If i = 5 then all of the grandchildren have degree 4 or 5. Any grandchild x of degree 4 must have 3 edges to vertices of degree 5 which don't have a parent of degree 4. It follows x has edges to two vertices with the same parent, and there is a square.
If i = 6 a similar argument shows that all of the grandchildren of degree 4 must have edges to the grandchild p 2 of degree 6, and p 2 has a parent of degree 4 (or a similar argument applies). So we have the situation illustrated in Figure 10. Note that p 2 is adjacent to all of the grandchildren of degree 4 and two of the grandchildren of degree 5, x 1 and x 2 . Now the grandchildren of degree 4 are each adjacent to p 2 and two of the grandchildren of degree 5 that have a parent of degree 5. Thus the vertices in π 1 and π 2 are at a distance greater than 2 from p 2 unless they are adjacent to x 1 or x 2 . At most two elements of π 1 ∪ π 2 can have edges to x 1 or x 2 , so at least two vertices are at a distance greater than 2 from p 2 , which is impossible as p 2 is the root of an embedded S 6, [4,4,4,3,3,3] star (which contains 27 of the vertices). Proof From Theorem 11 any extremal graph Γ on 29 vertices can be constructed by adding a new vertex x, and edges to a set of 4 vertices that is a set in S Γ ,4 , where Γ is one of the 4 extremal graphs on 28 vertices. There are 7 potential graphs Γ. All of these graphs are shown to be isomorphic, using nauty, and the single graph was shown to satisfy the stated property.
Proof We know from Table 1  Proof From Theorem 12 any extremal graph Γ on 30 vertices can be constructed by adding a new vertex x, and edges to a set of 4 vertices that is a set in S Γ ,4 , where Γ is the extremal graphs on 29 vertices. There are 2 potential graphs Γ, which are shown to be isomorphic, using nauty, and the single graph was shown to satisfy the stated properties.
Proof Suppose that Γ had 81 edges, then we must have δ = 5. Since the extremal graph Γ on 29 vertices with 76 edges has empty set S Γ ,5 , this is not possible. So there are at most 80 edges. We know from Table 1 [4,4,4,4,4,3] stars, each of which has children from both elements, s 1 and s 2 say, of S Γ ,4 . In the first star the child from s 1 has degree 4 and the child from s 2 has degree 5, and in the second star, the reverse is true. The result follows.
Proof We know from Table 1 that in this case all vertices have degree 5 or 6. There are 22 vertices of degree 5 and 10 vertices of degree 6.
Suppose that no vertex of degree 6 has a neighbour of degree 6. Then every vertex of degree 6 has 6 neighbours of degree 5. The sets of neighbours of each of the vertices of degree 6 form a linear space on 22 points with 10 blocks of size 6, contradicting Lemma 6.
we can construct all graphs by adding a new vertex x and edges to a set of 5 vertices that is a set in S Γ ,5 , where Γ is an extremal graph on 30 vertices. There are two such graphs, and in each case S Γ ,5 contains 1 element. So there are 2 potential graphs. These are shown to be isomorphic.
There are 10 sets of 3 non-intersecting elements of S Γ,3 . These are shown in Table 4. In each case, at least 2 of the vertices of degree 4 not contained in any set are in an edge with a vertex that is in one of the sets.