A square-free graph is a finite simple graph containing no graph cycles of length four, including those with cycle chords. A simple graph is square-free iff
![c_4=1/8[Tr(A^4)-2m-2sum_(i!=j)a_(ij)^((2))]=0,](/images/equations/Square-FreeGraph/NumberedEquation1.svg) |
where 
is the adjacency matrix of the graph, 
is the matrix trace, 
is the number of edges of the graph,
and 
denotes the 
element of 
.
The numbers of square-free simple graphs up to graph isomorphism on 
, 2, 3, ... nodes
are 1, 2, 4, 8, 18, 44, 117, 351, ... (OEIS A006786),
the first few of which are illustrated above.
The numbers of connected square-free simple graphs up to graph isomorphism on 
, 2, 3, ... nodes
are 1, 1, 2, 3, 8, 19, 57, ... (OEIS A077269),
the first few of which are illustrated above.
Graphs with girth greater than 4 are square-free. A square-free graph can also have girth 3, for example the triangle graph.
The enumeration with fixed vertex labels has a sharp asymptotic form. Yang (2026) proved that the number of square-free graphs
on the labeled vertex set 
is
 |
Here 
denotes little-o notation. Unlike the
counts above, these count distinct labelings separately. The result answers the four-cycle
case of the forbidden-subgraph counting question related to Erdős
problem 59.
-Free Graphs." 29 Oct 2026.