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}$
- $\Delta $
- 2$\Delta $ -2
- $\Delta ^{2}$
- |V|
- 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}$
- $| V | - 1$
- $| E | - 1$
- $|E| \cdot (| V | - 1)$
- $|E|^{2} \cdot | V |$
- 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