edge-coloring and vertex-coloring reduction problem

Question

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

Answer 1

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)$.

Answer 2

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.