Given your constraints, I might be inclined to try going about it the other way: find all paths that have no more than one edge of any color, and check each one to see if it is (or contains) a cycle.

Given C colors, and about N edges of each color, the number of edge sets to consider is O(N^C), which isn't too bad.