# Color coding to get an FPT algoirthm for $k$ disjoint triangles

Consider the following problem:

Input: A graph $$G=(V,E)$$ and an integer $$k \in \mathbb{N}$$

Output: Are there $$k$$ vertex-disjoint triangles in $$G$$?

Assume we want to use color coding to develop an FPT Algorithm for that, as done here (starting from slide 60). The reference material proposes the following method:

1. Choose a random coloring $$V \rightarrow [3k]$$
2. Check if there is a colorful solution where the $$3k$$ vertices of the $$k$$ triangles use distinct colors.

For 2. it proposes this, amongst others, this method:

Try every permutation $$\pi$$ of $$[3k]$$ and check if there are triangles with colors $$(\pi(1), \pi(2), \pi(3)), (\pi(4),\pi(5),\pi(6), \dots)$$

I don’t understand why we have to check every permutation $$\pi$$ of the colors. Wouldn’t it be enough to just to check each triple of vertices, see if there are a triangle and if so, only count this triangle if it only uses colors we have not seen before? So like so:

1. For each triple $$x,y,z \in V$$:
2. If $$x,y,z$$ form a triangle and colors $${c(x),c(y),c(z)}$$ not in colors_seen_so_far:

2.1 colors_seen_so_far += $$\{c(x), c(y), c(z)\}$$

2.2 num_triangles += 1

where we initialize colors_seen_so_far = $$\emptyset$$ and num_triangles = $$0$$