# edge-coloring and vertex-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve.

That's the problem:

Edge-Coloring problem, 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?". 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} Let's look at reduction, Edge-Coloring $$\leq _p$$ Vertex-Coloring According to the graph G = (V, E), built new vertices Group: $$\widetilde{V}$$ = {$$x_e | e \in E$$} We will define a new edge between two vertices, $$x_{e_1}$$ and $$x_{e_2}$$, if there is a common vertex between edges $$e_1$$ and $$e_2$$. $$\widetilde{E}$$ = {$$(x_{e_1},x_{e_2}) | e_1 \cap e_2 \neq \phi$$} Finally we will define: $$\widetilde{G}$$ = ($$\widetilde{V}$$ , $$\widetilde{E}$$)

The question has 2 parts, but they are related to each other, so I can not ask each question separately.

Section A

We will mark the maximum degree (of all the vertices of G) in $$\Delta$$ . Which of the following is the closest bound (or barrier) to the maximum degree of $$\widetilde{G}$$

1. $$\Delta$$
2. 2$$\Delta$$ -2
3. $$\Delta ^{2}$$
4. |V|
5. none of the answers is correct.

I think the answer is 2, if there is a vertex in $$G$$, with degree $$\Delta$$. When doing a reduction to $$\widetilde{G}$$ each edge becomes a vertex, because an edge can be connected to 2 vertices, and these 2 vertices are connected to the other edges, so it makes sense. But I can not rule out the answer 3, because it has a bigger bound(or barrier) and I can not rule out it.

Answer 1 is incorrect, because in my opinion 2 is correct. Answer 4 is incorrect, but fails to explain it logically.

Section B

Recall that the maximum degree $$D \leq | V | - 1$$. Which of the following is the closest bound (or barrier) to the number of edges in $$\widetilde{E}$$

1. $$| V | - 1$$
2. $$| E | - 1$$
3. $$|E| \cdot (| V | - 1)$$
4. $$|E|^{2} \cdot | V |$$
5. none of the answers is correct.

I think the answer is 3. If in G there is a complete graph, that all the vertices are connected to all the other vertices, the degree of each vertex is $$D = |V|-1$$, so in $$\widetilde{G}$$ there will be up to $$|V|-1$$ for each vertex of G. The number of vertices in G is |E|, so the answer comes out 3. In my opinion

But I can not say why answer 4. is incorrect.

The question was translated from Hebrew. So I have no source for the question. I have asked a similar question before, but there are other questions here, so I ask again

• – D.W.
Oct 26 at 3:39
• You can still credit the original source: e.g., a book, a specific class, a web page. Nothing about translating from another language prevents you from crediting your sources.
– D.W.
Oct 26 at 3:39

Regarding the first part.

Answer 1 is incorrect. Consider the graph $$G = (\{1,2,3,4,5,6\}, \{(1,2), (1,3), (2,3), (3,4), (4, 5), (4,6) \})$$. The maximum degree of $$G$$ is $$3$$ but the degree of $$x_{(3,4)}$$ in $$\widetilde{G}$$ is $$4$$.

Answer 2 is correct. Consider an edge $$e=(u,v)$$ of $$G$$. The number edges distinct from $$e$$ that are incident to $$u$$ (resp. $$v$$) is at most $$\Delta-1$$, therefore the degree of $$x_e$$ in $$\widetilde{G}$$ is at most $$2(\Delta-1)$$.

Answers 3 is incorrect because the question asks for the tightest upper bound and, for $$\Delta \ge 1$$, $$2\Delta -2 = 2(\Delta-1) \le \Delta(\Delta-1) < \Delta^2$$.

Answer $$4$$ is incorrect. Consider the graph $$G = (\{1,2,3,4,5\}, \{ (1,2), (1,3), (2,3), (4, 5), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3) \})$$. Here $$|V|=5$$ but the degree of $$x_{(4,5)}$$ in $$\widetilde{G}$$ is $$6$$.

Regarding the second part:

Answer 1 is incorrect, as shown by the second counterexample above.

Answer 2 is incorrect, as shown by the fist counterexample above (the degree of $$x_{(1,2)}$$ is $$2$$, the degree of $$x_{(1,4)}$$ is $$4$$, $$x_{(1,2)}$$ and $$x_{(1,4)}$$ are not neighbors, therefore the number of edge of $$\widetilde{G}$$ is at least $$6$$, but $$|E|-1=5$$).

Answer 3 immediately follows from part $$1$$. The sum of degrees is $$\widetilde{G}$$ is at most $$|E|(2\Delta - 2)$$. Since the number of edges is exactly half the sum of the degrees you get the desired bound.

Answer $$4$$ is not the tightest bound among the options given since, for graphs with at least one edge, $$|E|^2 \cdot |V| > |E|(V-1)$$.

Let's check these in reverse order.

• Question B: your reasoning looks good as it demonstrates that both (1) and (2) are not strong enough. The choice (4) is a possible bound, but it's not as tight as it can be. Your example is extremal in a sense that you can't make the degrees any larger, meaning that your bound is, as the question asks, "closest possible".

• Question A: You are right that $$2\Delta-2$$ is the closest bound. Again, other bounds might also be possible, but they are not as tight.