Girth greater than 4

ex(n;4)

P.Erdös <ref>P. Erdös, Some recent progress on the extremal problems in graph theory, Congr. Numer. 14 (1975) 3--14</ref> conjectured that ex(n;4)=(1/2 + o(1))^3/2 n^3/2.

Garnick et al. demonstrated that extremal graphs include:

• Stars K_1,n-1 and Paths P_n for n  ≤  4,
• Moore graphs:
  • EX(5;4)={C₅} the cycle;
  • ex(10;4)= 15 is attained by the Petersen graph ;
  • ex(50;4)=175 is attained by the Hoffman-Singleton graph;
  • ex(3250;4) is attained by the Moore graph with girth 5 and degree 57 if it exists.
• C₆ is an element of EX(6;4).
• polarity graphs.

Let G be an extremal graph of order n. Then

1. the diameter of G is at most 3;
2. if d(x)=δ(G)=1, then the graph G-{x} has diameter at most 2.

The following table lists the known values and constructive lower bounds for ex(n;4). If the value is known then it is shown in bold text.

Known values and constructive lower bounds for ex(n;4)

n	0	1	2	3	4	5	6	7	8	9
0	0	0	1	2	3	5	6	8	10	12
10	15	16	18	21	23	26	28	31	34	38
20	41	44	47	50	54	57	61	65	68	72
30	76	80	85	87	90	94	99	104	109	114
40	120	124	129	134	139	144	150	156	162	168
50	175	176	178	181	185	188	192	195	199	203
60	207	212	216	221	226	231	235	240	245	250
70	255	260	265	270	275	280	285	291	296	301
80	306	311	317	323	329	334	340	346	352	357
90	363	368	374	379	385	391	398	404	410	416
100	422	428	434	440	446	452	458	464	470	476
110	483	489	495	501	508	514	520	526	532	538
120	544	551	558	565	571	578	584	590	596	603
130	610	617	623	630	637	644	651	658	665	672
140	679	686	693	700	707	714	721	728	735	742
150	749	756	763	770	777	784	791	798	805	812
160	819	826	834	841	849	856	863	871	878	886
170	893	901	909	917	925	933	941	948	956	963
180	971	979	986	994	1001	1009	1017	1025	1033	1041
190	1049	1057	1065	1073	1081	1089	1097	1105	1113	1121
200	1129

The following table is the key to the colors in the table presented above:

Color	References
*	Garnick, Kwong and Lazebnik<ref>D. K. Garnick and Y. H. H. Kwong, F. Lazebnik, Extremal graphs without three-cycles or four-cycles, J. Graph Theory, 17 (1993), 633--645</ref>.
*	Garnick and Nieuwejaar<ref>D. K. Garnick and N.A. Nieuwejaar, Non-isomorphic extremal graphs without three-cycles or four-cycles, JCMCC, 12 (1992), 33--56</ref>.