Graph is obtained by adding vertex to and making adjacent to every vertex of . The minimum number of colours required to edge-colour is ________.
GATE CS 2020 (Forenoon) — Question 62
Discrete MathematicsAdvanced Graph Bounds (Matching, Coloring Theorems)NAT2 marksMedium
A GATE question every morning
One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.
More on Advanced Graph Bounds (Matching, Coloring Theorems)
- GATE CS 2026 (Forenoon) · Q47Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V' V such that for every (u, v) E , u V' or v V' . Let the size…
- GATE CS 2024 (Forenoon) · Q51The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let G be any graph with n vertice…
- GATE CS 2024 (Afternoon) · Q60The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the follo…
- GATE CS 2023 (Forenoon) · Q55Let G be a simple, finite, undirected graph with vertex set \ v 1, , v n\ . Let (G) denote the maximum degree of G and let N = \ 1, 2, \ de…
- GATE CS 2022 (Forenoon) · Q50The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE?
- GATE CS 2018 (Forenoon) · Q28The chromatic number of the following graph is .

