# Extremal Graphs and Turan numbers

If H is a set of graphs, then an extremal graph with respect to H is a graph having the largest possible number of edges without containing any subgraph isomorphic to a graph in H. The number of edges in an extremal graph on n vertices is called the Turan number of H and sometimes is denoted ex(n,H).

In specifying H, Ck is a cycle with k vertices and Codd means all odd cycles. As everyone knows, a graph has no odd cycles iff it is bipartite.

The extremal graphs for H={C3} and H={Codd} are the complete bipartite graphs with sides as nearly equal as possible. For H containing only a clique of order k, Turan's famous theorem says that the extremal graphs are the complete multipartite graphs with k-1 parts as nearly equal as possible.

When H consists of a single odd cycle, the extremal graphs for sufficiently large n are the complete bipartite graphs with sides as nearly equal as possible. The complete details for all n were worked out by Zoltan Füredi and David Gunderson.

Apart from these examples, almost nothing is known apart from examples for small n and some asymptotic and comparative results.

On this page we provide the extremal graphs for small n when H is a collection of cycles. It is the joint work of Narjess Afzaly and Brendan McKay. In all cases apart from those mentioned above, our tables go further than was previously known. Details of what was known earlier will appear in our papers in preparation.

The meanings of the table entries are:

• nv = the number of vertices
• ne = the number of edges (the Turan number)
• ng = the number of graphs with ne edges. This is linked to a file giving the graphs in sparse6 format.

If neither ne nor ng is preceded by "≥", it means that we have the Turan number exactly and all the extremal graphs.

If ne is not preceded by "≥" but ng is preceded by "≥", it means that we have the Turan number exactly but possibly there are more extremal graphs. In this case, the file name contains the word "some".

If the values of both ne and ng are preceded by "≥", it means that we are giving all the graphs we can find on the largest number of edges we can find, but we didn't prove that that more edges are impossible. In this case, the file name contains the word "maybe".

In all cases where we didn't prove that all the extremal graphs are present, we are confident that we have them all and would like to know of any exceptions.

## H={C4}

These are the extremal graphs without 4-cycles. ALL

 nv ne ng
 4 4 1
 5 6 1
 6 7 4
 7 9 5
 8 11 5
 9 13 10
 10 16 2
 11 18 11
 12 21 3
 13 24 2
 14 27 1
 15 30 2
 16 33 2
 17 36 1
 18 39 1
 19 42 5
 20 46 1
 21 50 1
 22 52 13
 23 56 1
 24 59 20
 25 63 9
 26 67 8
 27 71 7
 28 76 1
 29 80 2
 30 85 1
 31 90 1
 32 92 9
 33 96 18
 34 102 1
 35 106 1
 36 110 5
 37 113 11
 38 117 ≥20
 39 122 ≥1
 40 127 ≥2

 41 ≥132 ≥3
 42 ≥137 ≥3
 43 ≥142 ≥7
 44 ≥148 ≥2
 45 ≥154 ≥1
 46 ≥157 ≥9
 47 ≥163 ≥1
 48 ≥168 ≥10
 49 ≥174 ≥6

## H={C5}

These are the extremal graphs without 5-cycles. The unique extremal graph for n≥8 is the balanced complete bipartite graph. ALL

 nv ne ng
 5 7 2
 6 9 3
 7 12 2
 8 16 1

## H={C6}

These are the extremal graphs without 6-cycles. ALL

 nv ne ng
 6 11 1
 7 13 1
 8 16 1
 9 20 1
 10 21 3
 11 23 3
 12 26 3
 13 30 2
 14 31 7
 15 33 11
 16 37 1
 17 40 4
 18 41 32
 19 44 8
 20 48 2
 21 50 12
 22 52 16
 23 56 2
 24 59 1
 25 61 1
 26 64 3
 27 67 9
 28 70 1
 29 72 3
 30 76 1
 31 78 10
 32 80 70
 33 84 4
 34 87 1
 35 89 49
 36 92 ≥60
 37 95 ≥125

 38 ≥98 ≥258
 39 ≥101 ≥292
 40 ≥105 ≥7
 41 ≥108 ≥10

## H={C7}

These are the extremal graphs without 7-cycles. The unique extremal graph for n≥12 is the balanced complete bipartite graph. ALL

 nv ne ng
 7 16 1
 8 18 2
 9 21 2
 10 25 2
 11 30 2
 12 36 1

## H={C8}

These are the extremal graphs without 8-cycles. ALL

 nv ne ng
 8 22 1
 9 24 1
 10 27 1
 11 31 1
 12 36 1
 13 42 1
 14 43 3
 15 45 3
 16 48 3
 17 52 3
 18 57 3
 19 63 2
 20 64 7
 21 66 8
 22 69 8
 23 73 8
 24 78 8
 25 84 4
 26 85 22
 27 87 24
 28 90 28
 29 95 3
 30 101 1
 31 105 9
 32 106 66
 33 108 86
 34 112 12
 35 117 12
 36 123 3
 37 126 22

 38 ≥127 ≥240

## H={C9}

These are the extremal graphs without 9-cycles. The unique extremal graph for n≥16 is the balanced complete bipartite graph. ALL

 nv ne ng
 9 29 1
 10 31 1
 11 34 2
 12 38 2
 13 43 1
 14 49 2
 15 56 2
 16 64 1

## H={C11}

These are the extremal graphs without 11-cycles. The unique extremal graph for n≥20 is the balanced complete bipartite graph. ALL

 nv ne ng
 11 46 1
 12 48 1
 13 51 1
 14 55 2
 15 60 2
 16 66 1
 17 73 1
 18 81 2
 19 90 2
 20 100 1

## H={C3,C4}

These are the extremal graphs of girth at least 5. ALL

 nv ne ng
 5 5 1
 6 6 2
 7 8 1
 8 10 1
 9 12 1
 10 15 1
 11 16 3
 12 18 7
 13 21 1
 14 23 4
 15 26 1
 16 28 22
 17 31 14
 18 34 15
 19 38 1
 20 41 1
 21 44 3
 22 47 3
 23 50 7
 24 54 1
 25 57 6
 26 61 2
 27 65 1
 28 68 4
 29 72 1
 30 76 1
 31 80 2
 32 85 1
 33 87 12
 34 90 237
 35 95 5
 36 99 36
 37 104 7
 38 109 2
 39 114 1
 40 120 1
 41 124 1
 42 129 1
 43 134 1
 44 139 2
 45 145 1
 46 150 2
 47 156 1
 48 162 1
 49 168 1
 50 175 1
 51 176 7
 52 178 148
 53 181 ≥2688

 54 ≥185 ≥13
 55 ≥189 ≥5
 56 ≥193 ≥11
 57 ≥197 ≥4
 58 ≥202 ≥1
 59 ≥207 ≥2
 60 ≥212 ≥2
 61 ≥216 ≥17
 62 ≥220 ≥85
 63 ≥224 ≥6065
 64 ≥230 ≥6

## H={C3,C4,C5}

These are the extremal graphs of girth at least 6. ALL

 nv ne ng
 3 2 1
 4 3 2
 5 4 3
 6 6 1
 7 7 2
 8 9 1
 9 10 4
 10 12 3
 11 14 1
 12 16 1
 13 18 1
 14 21 1
 15 22 3
 16 24 4
 17 26 4
 18 29 1
 19 31 1
 20 34 1
 21 36 3
 22 39 2
 23 42 1
 24 45 1
 25 48 1
 26 52 1
 27 53 4
 28 56 1
 29 58 1
 30 61 1
 31 64 1
 32 67 5
 33 70 3
 34 74 1
 35 77 1
 36 81 1
 37 84 3
 38 88 2
 39 92 1
 40 96 1
 41 100 1
 42 105 1
 43 106 5
 44 108 12
 45 110 183
 46 115 1
 47 118 1
 48 122 1
 49 126 1
 50 130 1
 51 134 1
 52 138 3
 53 142 3
 54 147 1
 55 151 1
 56 156 1
 57 160 3
 58 165 2
 59 170 1
 60 175 1
 61 180 1
 62 186 1
 63 187 6
 64 189 ≥31

## H={C3,…,C6}

These are the extremal graphs of girth at least 7. ALL

 nv ne ng
 3 2 1
 4 3 2
 5 4 3
 6 5 6
 7 7 1
 8 8 2
 9 9 7
 10 11 1
 11 12 7
 12 14 2
 13 15 15
 14 17 3
 15 18 55
 16 20 13
 17 22 3
 18 23 174
 19 25 48
 20 27 18
 21 29 5
 22 31 3
 23 33 2
 24 36 1
 25 37 9
 26 39 6
 27 41 3
 28 43 2
 29 45 1
 30 47 1
 31 49 1
 32 51 5
 33 53 8
 34 55 20
 35 58 1
 36 59 205
 37 61 392
 38 63 1415
 39 66 1
 40 68 11
 41 70 54
 42 72 420
 43 74 3152
 44 77 5
 45 79 22
 46 81 490
 47 83 9094
 48 86 54
 49 88 ≥1049
 50 91 ≥29
 51 94 ≥3
 52 96 ≥13

 53 ≥98 ≥52
 54 ≥100 ≥669
 55 ≥103 ≥9
 56 ≥105 ≥191

## H={C3,…,C7}

These are the extremal graphs of girth at least 8. ALL

 nv ne ng
 3 2 1
 4 3 2
 5 4 3
 6 5 6
 7 6 11
 8 8 1
 9 9 2
 10 10 8
 11 12 1
 12 13 5
 13 14 29
 14 16 4
 15 18 1
 16 19 6
 17 20 65
 18 22 6
 19 24 2
 20 25 32
 21 27 2
 22 29 1
 23 30 37
 24 32 6
 25 34 2
 26 36 2
 27 38 1
 28 40 1
 29 42 1
 30 45 1
 31 46 3
 32 47 44
 33 49 4
 34 51 5
 35 53 1
 36 55 1
 37 56 73
 38 58 27
 39 60 26
 40 63 1
 41 64 75
 42 66 35
 43 68 32
 44 70 21
 45 72 36
 46 75 3
 47 77 1
 48 80 1
 49 81 9
 50 83 2
 51 85 4
 52 87 26
 53 90 1
 54 92 2
 55 94 5
 56 96 ≥9
 57 98 ≥37

 58 ≥100 ≥135
 59 ≥103 ≥2
 60 ≥105 ≥27

## H={C3,…,C8}

These are the extremal graphs of girth at least 9. ALL

 nv ne ng
 5 4 3
 6 5 6
 7 6 11
 8 7 23
 9 9 1
 10 10 2
 11 11 8
 12 12 28
 13 14 1
 14 15 8
 15 16 57
 16 18 3
 17 19 24
 18 21 1
 19 22 14
 20 23 240
 21 25 4
 22 27 1
 23 28 11
 24 29 358
 25 31 2
 26 33 1
 27 34 23
 28 35 1693
 29 37 16
 30 39 1
 31 40 152
 32 42 4
 33 43 1092
 34 45 28
 35 47 1
 36 48 501
 37 50 25
 38 52 2
 39 54 1
 40 55 116
 41 57 5
 42 58 3202
 43 60 379
 44 62 51
 45 64 6
 46 65 5692
 47 67 1134
 48 69 311
 49 71 75
 50 73 22
 51 75 7
 52 77 4
 53 78 ≥2015
 54 80 ≥77
 55 82 ≥16
 56 84 ≥1

 57 ≥85 ≥2572
 58 ≥87 ≥205

## H={C3,…,C9}

These are the extremal graphs of girth at least 10. ALL

 nv ne ng
 5 4 3
 6 5 6
 7 6 11
 8 7 23
 9 8 47
 10 10 1
 11 11 2
 12 12 9
 13 13 31
 14 15 1
 15 16 5
 16 17 37
 17 18 227
 18 20 5
 19 21 39
 20 23 1
 21 24 16
 22 25 232
 23 27 1
 24 28 58
 25 30 2
 26 31 38
 27 32 1198
 28 34 10
 29 36 2
 30 37 39
 31 38 1313
 32 40 10
 33 42 1
 34 43 33
 35 44 2599
 36 46 26
 37 48 1
 38 49 75
 39 51 1
 40 52 313
 41 54 8
 42 55 1382
 43 57 8
 44 59 1
 45 60 277
 46 62 3
 47 63 1612
 48 65 30
 49 67 1
 50 68 1096
 51 70 25
 52 71 24959
 53 73 612
 54 75 31
 55 76 46794
 56 78 1930
 57 80 75
 58 82 4
 59 84 1
 60 85 ≥945
 61 87 ≥33
 62 89 ≥3

 63 ≥90 ≥13524
 64 ≥92 ≥2412

## H={C3,C6}

These are the extremal graphs without 3-cycles or 6-cycles. ALL

 3 2 1
 4 4 1
 5 6 1
 6 8 1
 7 10 1
 8 12 1
 9 14 1
 10 16 1
 11 18 1
 12 20 1
 13 22 1
 14 24 1
 15 26 1
 16 28 3
 17 30 12
 18 33 1
 19 35 5
 20 38 1
 21 40 4
 22 42 44
 23 45 6
 24 48 2
 25 51 1
 26 53 15
 27 56 5
 28 59 2
 29 62 1
 30 64 19
 31 67 3
 32 70 3
 33 72 67
 34 75 44
 35 78 24
 36 82 1
 37 84 19
 38 87 12
 39 90 4
 40 93 4
 41 96 5
 42 99 6
 43 102 ≥10
 44 106 ≥3
 45 110 ≥2

 46 ≥112 ≥34
 47 ≥115 ≥17

## H={C3,C8}

Up to 53 vertices, K3,n-3 is the unique extremal graph without 3-cycles or 8-cycles. On 54 vertices, it is extremal but it is possible, though unlikely, that there is another. This pattern does not continue forever, but we don't know when it stops.

## H={C4,C5}

These are the extremal graphs without 4-cycles or 5-cycles. ALL

 nv ne ng
 4 4 1
 5 6 1
 6 7 3
 7 9 2
 8 10 10
 9 12 8
 10 14 4
 11 16 4
 12 18 7
 13 20 9
 14 23 1
 15 25 2
 16 28 1
 17 30 1
 18 33 1
 19 35 1
 20 38 1
 21 42 1
 22 43 3
 23 45 7
 24 48 5
 25 50 17
 26 53 3
 27 55 119
 28 58 38
 29 62 1
 30 65 1
 31 67 5
 32 70 2
 33 73 2
 34 77 1
 35 79 11
 36 82 18
 37 86 4
 38 89 5
 39 93 3
 40 96 4
 41 100 2
 42 105 2
 43 107 5
 44 110 ≥1

 45 ≥114 ≥1
 46 ≥117 ≥1
 47 ≥121 ≥1
 48 ≥124 ≥2

## H={C4,C6}

These are the extremal graphs without 4-cycles or 6-cycles. ALL

 nv ne ng
 4 4 1
 5 6 1
 6 7 3
 7 9 2
 8 10 7
 9 12 4
 10 13 25
 11 15 12
 12 17 3
 13 19 1
 14 21 1
 15 22 63
 16 24 57
 17 26 57
 18 28 92
 19 30 159
 20 32 291
 21 35 1
 22 37 8
 23 39 36
 24 41 172
 25 44 2
 26 46 14
 27 48 95
 28 50 869
 29 53 25
 30 56 1
 31 58 20
 32 60 284
 33 63 11
 34 66 1
 35 69 1
 36 72 1
 37 74 2
 38 77 1
 39 79 5
 40 81 21
 41 83 45
 42 85 ≥195
 43 88 ≥2
 44 90 ≥132

 45 ≥93 ≥4
 46 ≥95 ≥288
 47 ≥98 ≥6
 48 ≥100 ≥1199
 49 ≥103 ≥69

## H={C4,C7}

These are the extremal graphs without 4-cycles or 7-cycles. ALL

 nv ne ng
 4 4 1
 5 6 1
 6 7 4
 7 9 3
 8 10 16
 9 12 8
 10 15 1
 11 16 1
 12 18 1
 13 19 6
 14 21 7
 15 23 2
 16 24 80
 17 26 35
 18 29 2
 19 31 1
 20 34 1
 21 36 3
 22 39 2
 23 42 1
 24 45 1
 25 48 1
 26 52 1
 27 53 2
 28 56 1
 29 58 1
 30 61 1
 31 64 1
 32 67 5
 33 70 3
 34 74 1
 35 77 1
 36 81 1
 37 84 3
 38 88 2
 39 92 1
 40 96 1
 41 100 1
 42 105 1
 43 106 3
 44 108 13
 45 110 183
 46 115 1
 47 118 1
 48 122 1
 49 126 1
 50 130 1
 51 134 1
 52 138 3
 53 142 3
 54 147 1
 55 151 1
 56 156 1
 57 160 3
 58 165 2
 59 170 1
 60 175 1
 61 180 1
 62 186 1
 63 187 3

 64 ≥189 ≥32

## H={C4,C8}

These are the extremal graphs without 4-cycles or 8-cycles. ALL

 4 4 1
 5 6 1
 6 7 4
 7 9 5
 8 11 2
 9 12 33
 10 14 14
 11 15 245
 12 17 94
 13 19 10
 14 20 852
 15 22 168
 16 23 9473
 17 25 2580
 18 27 570
 19 29 304
 20 31 94
 21 33 12
 22 34 13644
 23 36 3257
 24 38 980
 25 40 490
 26 42 140
 27 44 16
 28 46 8
 29 48 13
 30 50 27
 31 52 54
 32 54 73
 33 56 64
 34 58 35
 35 59 215178
 36 61 78616
 37 63 ≥18492
 38 65 ≥15366
 39 67 ≥31057

 40 ≥69 ≥62535

## H={C5,C6}

These are the extremal graphs without 5-cycles or 6-cycles. ALL

 nv ne ng
 5 7 2
 6 9 2
 7 12 1
 8 13 6
 9 15 6
 10 18 2
 11 19 17
 12 21 19
 13 24 4
 14 25 76
 15 28 3
 16 30 20
 17 32 38
 18 35 5
 19 38 2
 20 41 2
 21 43 6
 22 46 2
 23 49 1
 24 52 2
 25 54 7
 26 57 2
 27 60 1
 28 63 2
 29 67 1
 30 69 3
 31 72 1
 32 74 3
 33 78 1
 34 81 1
 35 83 8
 36 86 3
 37 88 44
 38 92 3
 39 96 1
 40 100 1
 41 102 1
 42 104 ≥6

## H={C3,C4,C6}

These are the extremal graphs cycles of length 3, 4 or 6. ALL

 3 2 1
 4 3 2
 5 5 1
 6 6 1
 7 7 5
 8 9 1
 9 10 5
 10 12 2
 11 13 16
 12 15 5
 13 17 2
 14 18 62
 15 20 33
 16 22 19
 17 24 12
 18 27 1
 19 28 9
 20 30 7
 21 32 11
 22 34 16
 23 36 16
 24 38 13
 25 40 25
 26 42 48
 27 45 1
 28 46 487
 29 48 2162
 30 51 4
 31 53 26
 32 55 96
 33 57 1023
 34 60 2
 35 62 25
 36 65 1
 37 67 8
 38 69 139
 39 72 17
 40 75 3
 41 77 36
 42 80 10
 43 83 4
 44 86 2
 45 90 1
 46 91 21
 47 93 3
 48 95 ≥15

 49 ≥97 ≥88
 50 ≥100 ≥1

## H={C4,C6,C8}

These are the extremal graphs cycles of length 4, 6 or 8. ALL

 nv ne ng
 4 4 1
 5 6 1
 6 7 3
 7 9 2
 8 10 7
 9 12 4
 10 13 21
 11 15 8
 12 16 60
 13 18 19
 14 19 199
 15 21 55
 16 23 4
 17 25 1
 18 27 1
 19 28 12
 20 30 3
 21 31 317
 22 33 115
 23 35 34
 24 37 8
 25 39 2
 26 40 498
 27 42 218
 28 44 115
 29 46 62
 30 48 40
 31 50 36
 32 52 40
 33 54 50
 34 56 40
 35 58 36
 36 60 37
 37 62 55
 38 64 77
 39 66 92
 40 68 80
 41 70 71
 42 72 87
 43 74 169
 44 76 349
 45 78 816
 46 81 1
 47 83 4
 48 85 27
 49 87 ≥151
 50 90 1
 51 92 ≥2

 52 ≥94 ≥8
 53 ≥96 ≥54

## H={Codd,C4}

These are the extremal bipartite graphs of girth at least 6. ALL

Note how for these orders the maximum number of edges and often also the number of extremal graphs is the same as for H={C3,C4,C5}. We don't know if this is always true.

 nv ne ng
 4 3 2
 5 4 3
 6 6 1
 7 7 1
 8 9 1
 9 10 3
 10 12 3
 11 14 1
 12 16 1
 13 18 1
 14 21 1
 15 22 2
 16 24 4
 17 26 4
 18 29 1
 19 31 1
 20 34 1
 21 36 3
 22 39 2
 23 42 1
 24 45 1
 25 48 1
 26 52 1
 27 53 2
 28 56 1
 29 58 1
 30 61 1
 31 64 1
 32 67 5
 33 70 3
 34 74 1
 35 77 1
 36 81 1
 37 84 3
 38 88 2
 39 92 1
 40 96 1
 41 100 1
 42 105 1
 43 106 3
 44 108 12
 45 110 183
 46 115 1
 47 118 1
 48 122 1
 49 126 1
 50 130 1
 51 134 1
 52 138 3
 53 142 3
 54 147 1
 55 151 1
 56 156 1
 57 160 3
 58 165 2
 59 170 1
 60 175 1
 61 180 1
 62 186 1
 63 187 3
 64 189 ≥31

## H={Codd,C4,C6}

These are the extremal bipartite graphs of girth at least 8. ALL

 nv ne ng
 4 3 2
 5 4 3
 6 5 6
 7 6 11
 8 8 1
 9 9 1
 10 10 7
 11 12 1
 12 13 4
 13 14 22
 14 16 4
 15 18 1
 16 19 5
 17 20 47
 18 22 6
 19 24 2
 20 25 27
 21 27 2
 22 29 1
 23 30 33
 24 32 6
 25 34 2
 26 36 2
 27 38 1
 28 40 1
 29 42 1
 30 45 1
 31 46 2
 32 47 27
 33 49 4
 34 51 5
 35 53 1
 36 55 1
 37 56 68
 38 58 27
 39 60 26
 40 63 1
 41 64 65
 42 66 35
 43 68 32
 44 70 21
 45 72 36
 46 75 3
 47 77 1
 48 80 1
 49 81 6
 50 83 2
 51 85 4
 52 87 26
 53 90 1
 54 92 2
 55 94 5
 56 96 9
 57 98 37
 58 100 ≥135
 59 103 ≥2
 60 105 27
 61 108 3
 62 110 ≥9

 63 ≥112 ≥93
 64 ≥115 ≥5

## H={Codd,C4,C8}

These are the extremal bipartite graphs with 4-cycles or 8-cycles. ALL

 nv ne ng
 5 4 3
 6 6 1
 7 7 1
 8 9 1
 9 10 2
 10 12 1
 11 13 2
 12 15 1
 13 16 2
 14 18 1
 15 19 2
 16 21 1
 17 22 2
 18 24 1
 19 25 2
 20 27 1
 21 28 2
 22 30 1
 23 31 2
 24 33 1
 25 34 2
 26 36 1
 27 37 2
 28 39 1
 29 40 2
 30 42 1
 31 43 3
 32 45 2
 33 46 64
 34 48 13
 35 50 1
 36 52 1
 37 54 1
 38 57 1
 39 58 1
 40 60 1
 41 61 26
 42 63 23
 43 64 1020
 44 66 394
 45 68 2
 46 69 7931
 47 71 265
 48 73 28
 49 74 21420
 50 76 4003
 51 78 649
 52 80 ≥165
 53 82 ≥24
 54 84 ≥8
 55 86 ≥1

 56 ≥88 ≥2

## H={Codd,C4,C6,C8}

These are the extremal bipartite graphs of girth at least 10. ALL

 nv ne ng
 5 4 3
 6 5 6
 7 6 11
 8 7 23
 9 8 47
 10 10 1
 11 11 1
 12 12 8
 13 13 23
 14 15 1
 15 16 4
 16 17 29
 17 18 160
 18 20 5
 19 21 27
 20 23 1
 21 24 12
 22 25 158
 23 27 1
 24 28 49
 25 30 2
 26 31 33
 27 32 841
 28 34 10
 29 36 2
 30 37 31
 31 38 933
 32 40 10
 33 42 1
 34 43 28
 35 44 2090
 36 46 26
 37 48 1
 38 49 69
 39 51 1
 40 52 292
 41 54 8
 42 55 1260
 43 57 8
 44 59 1
 45 60 267
 46 62 3
 47 63 1575
 48 65 30
 49 67 1
 50 68 1079
 51 70 25
 52 71 24187
 53 73 612
 54 75 31
 55 76 45275
 56 78 1930
 57 80 75
 58 82 4
 59 84 1
 60 85 ≥928
 61 87 ≥33
 62 89 ≥3

 63 ≥90 ≥13407
 64 ≥92 ≥2412

## H={Codd,C6}

These are the extremal bipartite graphs without 6-cycles. ALL

 6 8 1
 7 10 1
 8 12 1
 9 14 1
 10 16 1
 11 18 1
 12 20 1
 13 22 1
 14 24 1
 15 26 1
 16 28 1
 17 30 1
 18 32 1
 19 34 1
 20 36 1
 21 38 1
 22 40 1
 23 42 1
 24 44 1
 25 46 1
 26 48 2
 27 50 3
 28 52 6
 29 54 15
 30 57 2
 31 60 3
 32 64 1
 33 66 1
 34 68 3
 35 70 6
 36 73 1
 37 76 2
 38 80 1
 39 82 2
 40 84 5
 41 86 12
 42 89 2
 43 92 5
 44 96 2
 45 100 1
 46 102 1
 47 104 3
 48 106 6
 49 109 1
 50 112 5
 51 116 1
 52 120 1
 53 122 2
 54 124 5
 55 126 12
 56 129 2
 57 132 9
 58 136 3
 59 140 2
 60 144 1
 61 146 1
 62 148 3
 63 150 ≥6
 64 153 ≥1

## H={Codd,C8}

For 5 ≤ n ≤ 63, the unique extremal bipartite graph with no cycle of length 8 is the complete bipartite graph K3,n-3. This situation does not continue forever, but we don't know when the pattern changes.

## H={Codd,C6,C8}

For n ≤ 55, the unique extremal bipartite graph with no cycle of length 6 or 8 is the complete bipartite graph K2,n-2. This situation does not continue forever, but we don't know when the pattern changes.

Page Master: Brendan McKay, brendan.mckay@anu.edu.au

Up to the combinatorial data page