A few days ago I had a test and could not pass it. This is a question I did not understand in the test.

> 
> We will look at the Edge-Coloring problem, in which, as is well known, we get as input graph G = (V, E) and natural number k and ask "Is there a coloration in arcs of G which uses at most k colors?". Remember, while painting vertices to two neighboring vertices must not have the same color, painting arcs to two neighboring arcs (i.e., having a common vertex) must not be
> The same color. That is, the language is:
> 
> 
> 

Edge-Coloring = {<G,k>|G can be arcuated by coloring using ≤ k colors}

> 
> Determine which of the following statements is correct:
> 
> 
> 1. The language is in P. An algorithm can be constructed running at time O (| V | \* | E |), by reduction to the vertex-Coloring problem and then verifying that each color is ≤ k.
> 2. The language is in NP (and it is also possible that it is NP-complete, but this is not due to the question data)
> 3. The language is NP-complete, which is why vertex-Coloring is NP-complete and also $Edge-coloring \leq \_pvertex-coloring $ can be performed by converting each arc to a vertex.
> 4. The language is NP-complete but not in NP
> 5. None of the above claims are true.
> 
> 
> 

I think 3 is true, because in my opinion a reduction is made from the vertex-coloring problem which is NPC, and also the edge-coloring problem should be in NPC.

But I can not rule out 4, 2 and 5.