GATE CSE 2020 | Question: 52

Question

Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______

Comments

If you know only basic then this answer is also good to understand how to solve this question :

1. Edge coloring for graph is assignment of colors to the graph edges such that no two incident edges have the same color.
2. here if asked for vertex coloring, the answer would be 3 (one color each for the two sets of vertices in given bipartite graph and 1 color for vertex 's')

3. This question is asking for edge coloring and not vertex coloring.

4. The vertex which is a part of highest number of incident edges is 's' as it has an edge to every other vertex of the graph. So there are 7 incident edges for this vertex and all of them need to be assigned a different/unique color.

5. So the minimum number of colors needed for edge coloring the given graph is 7

Answer 1

4 colors for edge coloring + 3 colors for the edges connecting the vertex s. The chromatic index or minimum edge colors are 7.

Answer 2

Edge colouring is = max degree of graph

here after adding edge the max degree of that graph will be 7 coz of new node

so ans is 7