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, like, say by computing the Lovasz number of the line graph of the graph?


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.



Complexity of edge coloring of class 1 graphs
As written the question is ill-posed: class 1 or class 2 is a property of a particular graph, whereas polynomial time is a property of an algorithm applied to an infinite family of graphs.


Patrick Schnider points out in the comments that the first fix to the question doesn't work: if we have a polynomial time algorithm for finding a colouring when it exists, we certainly have a polynomial time algorithm for testing whether a colouring exists.


The deeper question is perhaps this. Suppose we have an efficient algorithm for determining whether a particular structure (such as a colouring of a graph) exists. Can we use the algorithm to find it?


Sometimes the answer is yes. Suppose we have an efficient algorithm for deciding whether a graph is $k$-colourable. Then we can use it to find a $k$-colouring (when it exists) of a graph $G$ as follows. Test each non-edge $e$ of $G$ to see whether $G+e$ is also $k$-colourable. If it is, switch attention to $k$-colouring $G+e$. If it isn't, move on to the next edge. Note that we never have to test an edge more than once, as if $G+e$ is not $k$-colourable then $G+H+e$ is never $k$-colourable either, for any $H$. The end-point of this process is a complete $k$-partite graph, which is easily $k$-colourable.


But sometimes the answer is no, or at least "we don't know yet". Primality testing is in P, so we have an efficient algorithm to detect whether an integer can be factorised. But we don't have an efficient (classical) algorithm to factor integers, and it's not clear that we ever will. If there was a mechanical process to go from existence of objects to providing examples then this would not be such a notoriously difficult problem.


