However, the original graph may have up to \(n^{2.5}\)  4-cycles.This is because each edge may be in up to \(n\)  4-cycles. In particular, even after adding the dummy nodes between \(B\)  and \(C\) , there could still be up to \(n^{2.5}\)  4-cycles between \(A\)  and \(B\)  (4-cycles that use two nodes from \(A\)  and two nodes from \(B\) ), up to \(n^{2.5}\)  4-cycles between \(A\)  and \(C\) , and up to \(n^{2.5}\)  4-cycles that use two nodes from \(A\)  and one node from each of \(B\)  and \(C\) . None of these 4-cycles uses a dummy node, and therefore, the existence of a 4-cycle in the new graph doesn't necessarily imply the existence of a triangle in the original graph. We call these false 4-cycles.
Notably, this issue does not arise when reducing to \(k\) -cycle detection for odd \(k\)  (see [1]}) and it can be side-stepped easily in harder contexts such as the directedWhere the directions can prevent the existence of false cycles. or countingBy counting the number of 4-cycles in the induced graph on subsets of the three parts we can find out the exact number of false 4-cycles and then subtract it from the total number. versions or in other models [2]}, [3]}E.g. in databases a cycle can be forced by definition to use one node from each of the three parts and one dummy node..
Alas, such simple tricks do not work in the most basic case. As discussed in the introduction, this is not a mere technicality but the obstacle for gap amplification results.
