A square-free graph is a graph containing no graph cycles of length four. 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 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 square-free simple connected graphs 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 
are automatically square-free, while square-free graphs with girth 3 are rarer.
