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, C_k is a cycle with k vertices and C_odd means all odd cycles. As everyone knows, a graph has no odd cycles iff it is bipartite.

The extremal graphs for H={C₃} and H={C_odd} 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={C₄}

These are the extremal graphs without 4-cycles. ALL

102

106

110

113

117

122

127

≥132

≥137

≥142

≥148

≥154

≥157

≥163

≥168

≥174

H={C₅}

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

H={C₆}

These are the extremal graphs without 6-cycles. ALL

≥98

≥101

≥105

≥108

H={C₇}

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

H={C₈}

These are the extremal graphs without 8-cycles. ALL

101

105

106

108

112

117

123

126

≥127

≥240

H={C₉}

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

H={C₁₁}

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

100

H={C₃,C₄}

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

237

104

109

114

120

124

129

134

139

145

150

156

162

168

175

176

178

181

≥185

≥189

≥193

≥197

≥202

≥207

≥212

≥216

≥220

≥224

≥230

H={C₃,C₄,C₅}

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

100

105

106

108

110

183

115

118

122

126

130

134

138

142

147

151

156

160

165

170

175

180

186

187

189

≥31

H={C₃,…,C₆}

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

≥98

≥100

≥103

≥105

H={C₃,…,C₇}

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

≥100

≥103

≥105

H={C₃,…,C₈}

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

≥85

≥87

H={C₃,…,C₉}

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

≥90

≥92

H={C₃,C₆}

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

102

106

110

≥112

≥115

H={C₄,C₅}

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

119

100

105

107

110

≥114

≥117

≥121

≥124

H={C₄,C₆}

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

≥93

≥95

≥98

≥100

≥103

H={C₄,C₇}

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

100

105

106

108

110

183

115

118

122

126

130

134

138

142

147

151

156

160

165

170

175

180

186

187

≥189

≥32

H={C₄,C₈}

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

≥69

H={C₅,C₆}

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

100

102

104

≥6

H={C₃,C₄,C₆}

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

≥97

≥100

H={C₄,C₆,C₈}

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

≥94

≥96

H={C_odd,C₄}

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={C₃,C₄,C₅}. We don't know if this is always true.

100

105

106

108

110

183

115

118

122

126

130

134

138

142

147

151

156

160

165

170

175

180

186

187

189

≥31

H={C_odd,C₄,C₆}

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

100

≥135

103

≥2

105

108

110

≥9

≥112

≥93

≥115

≥5

H={C_odd,C₄,C₈}

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

≥88

H={C_odd,C₄,C₆,C₈}

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

≥90

≥92

H={C_odd,C₆}

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

100

102

104

106

109

112

116

120

122

124

126

129

132

136

140

144

146

148

150

≥6

153

≥1

H={C_odd,C₈}

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

H={C_odd,C₆,C₈}

For n ≤ 55, the unique extremal bipartite graph with no cycle of length 6 or 8 is the complete bipartite graph K_2,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

Extremal Graphs and Turan numbers

H={C4}

H={C5}

H={C6}

H={C7}

H={C8}

H={C9}

H={C11}

H={C3,C4}

H={C3,C4,C5}

H={C3,…,C6}

H={C3,…,C7}

H={C3,…,C8}

H={C3,…,C9}

H={C3,C6}

H={C4,C5}

H={C4,C6}

H={C4,C7}

H={C4,C8}

H={C5,C6}

H={C3,C4,C6}

H={C4,C6,C8}

H={Codd,C4}

H={Codd,C4,C6}

H={Codd,C4,C8}

H={Codd,C4,C6,C8}

H={Codd,C6}

H={Codd,C8}

H={Codd,C6,C8}

H={C₄}

H={C₅}

H={C₆}

H={C₇}

H={C₈}

H={C₉}

H={C₁₁}

H={C₃,C₄}

H={C₃,C₄,C₅}

H={C₃,…,C₆}

H={C₃,…,C₇}

H={C₃,…,C₈}

H={C₃,…,C₉}

H={C₃,C₆}

H={C₄,C₅}

H={C₄,C₆}

H={C₄,C₇}

H={C₄,C₈}

H={C₅,C₆}

H={C₃,C₄,C₆}

H={C₄,C₆,C₈}

H={C_odd,C₄}

H={C_odd,C₄,C₆}

H={C_odd,C₄,C₈}

H={C_odd,C₄,C₆,C₈}

H={C_odd,C₆}

H={C_odd,C₈}

H={C_odd,C₆,C₈}