The problem is to show that the graphs are the same or different up to relabeling of the vertices. I.e. the graphs

    0-1-2     0-2-1

are the same if you swap the labels 1 and 2. You could try to brute force it by trying all possible permutations of vertex labels, but there are n! of those to try, so that doesn't help much. Any polynomial-ish algorithm would need to do something clever that takes advantage of the structure of the problem.