We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it always imply that we have to find a polynomial time algorithm for the edge coloring of that graph? Like, is it possible to prove a graph to be in class $1$ without describing an explicit algorithm to do so?

Most of the problems I have seen invariably lead me to think that one could prove the graph is in class $1$ iff there is a polynomial time algorithm to color the edges of the graph. Is this right? Thanks beforehand.