Non-isomorphic Extremal Graphs without Three-Cycles or Four-Cycles

Abstract

We define an \({extremal \; graph}\) on \(v\) vertices to be a graph that has the maximum number of edges on \(v\) vertices, and that contains neither \(3\)-cycles nor \(4\)-cycles.
We establish that every vertex of degree at least \(3\), in an extremal graph of at least \(7\) vertices, is in a \(5\)-cycle; we enumerate all of the extremal graphs on \(21\) or fewer vertices; and we determine the size of extremal graphs of orders \(25\), \(26\), and \(27\).