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
$G$ is the complete tripartite graph $K_{1,3,4}$ (the new vertex $s$ is adjacent to everything in $K_{3,4}$).
- Maximum degree: $\deg(s)=7$, vertices in the part of size 3 have degree $4+1=5$, vertices in the part of size 4 have degree $3+1=4$. So $\Delta=7$.
- At least $\Delta=7$ colours are required for a proper edge colouring (the 7 edges at $s$ all meet).
- $G$ has 8 vertices (an even number) and edge-colourable with $\Delta$ colours (Class 1): the edge chromatic number is 7.
Minimum number of colours $=\mathbf7$.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2019 CS Q22
- GATE 2019 CS Q56
- GATE 2018 CS Q28
- GATE 2018 CS Q53
- GATE 2015 CS (CS1) Q44
- GATE 2017 CS (CS1) Q30
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →