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

Question

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$

Answer 1

No, this is not correct.

As a counterexample, suppose we have a graph consisting of a central triangle, together with 3 outer triangles, such that each outer triangle is joined to the central triangle by one shared vertex (i.e., each vertex of the central triangle is identified with one vertex of one of the outer triangles).

Clearly, a solution for $k=3$ would take the three outer triangles and not take the inner triangle.

Assume the random coloring assigns a distinct color to every vertex (otherwise there is no colorful solution).

If your greedy algorithm considers the central triangle first it will always take it, but this is incorrect.