GATE 2020 CS – Question 62
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 ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 7 to 7
Explanation
$s$ has degree 7, so at least 7 colours are needed. The remaining vertices have degree 4 or 5. $G$ has 8 vertices with edge chromatic number equal to the maximum degree Δ=7 (class 1), so 7 colours suffice.