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.
