The GATE Grind

GATE Engineering Mathematics: Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) – Previous Year Questions

46 GATE previous year questions on Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) (Engineering Mathematics, Computer Science) with answers and explanations, from every paper.

46 questions worth 75 marks in all (17 1-mark, 29 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q4 (1 mark, Multiple choice) – Let G be a nonplanar graph with the minimum possible number of edges. G has
  2. GATE 2007 CS Q23 (2 marks, Multiple choice) – Which graph has an Eulerian circuit?
  3. GATE 2008 CS Q23 (2 marks, Multiple choice) – Which is true for every planar graph on n vertices?
  4. GATE 2008 CS Q42 (2 marks, Multiple choice) – Graph G has n vertices and2n−2 edges partitionable into two edge-disjoint spanning trees. Which is NOT true?
  5. GATE 2009 CS Q2 (1 mark, Multiple choice) – What is the chromatic number of an n-vertex simple connected graph which does not contain any odd-length cycle? Assume n2.
  6. GATE 2009 CS Q3 (1 mark, Multiple choice) – Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
  7. GATE 2015 CS (CS2) Q61 (2 marks, Multiple choice) – A self-complementary graph is isomorphic to its complement. What must its vertex count n satisfy?
  8. GATE 2015 CS (CS2) Q62 (2 marks, Multiple choice) – A bridge is an edge whose removal disconnects a connected graph. Which is true?
  9. GATE 2010 CS Q11 (1 mark, Multiple choice) – For graph G=(V,E), let (G)= di dd, where i d counts vertices of degree d. If different trees S,T satisfy ξ(S)=ξ(T), what follows?
  10. GATE 2010 CS Q38 (2 marks, Multiple choice) – Which sequences cannot be degree sequences of simple graphs? I: 7,6,5,4,4,3,2,1 II: 6,6,6,6,3,3,2,2 III: 7,6,6,4,4,3,2,2 IV: 8,7,7,6,4,2,1,1
  11. GATE 2011 CS Q27 (1 mark, Multiple choice) – The drawings show complete graph K₄ and cube graph Q₃. Which is true?
  12. GATE 2013 CS Q35 (1 mark, Multiple choice) – For undirected graphs, P: The number of odd-degree vertices is even. Q: The sum of all vertex degrees is even. Which hold?
  13. GATE 2013 CS Q36 (2 marks, Multiple choice) – The line graph L(G) has one vertex per edge of simple G, and joins vertices iff their G edges share an endpoint. Which are always true? P: A cycle’s…
  14. GATE 2012 CS Q27 (1 mark, Multiple choice) – A connected simple planar graph has ten vertices and fifteen edges. How many bounded faces does any plane embedding have?
  15. GATE 2012 CS Q36 (2 marks, Multiple choice) – Which graph A,B,C,D is isomorphic to the given graph?
  16. GATE 2012 CS Q48 (2 marks, MTA) – A complete undirected graph has six labelled vertices. How many distinct cycles of length four does it contain?
  17. GATE 2017 CS (CS2) Q33 (1 mark, Numerical answer) – An undirected graph has n vertices, 25 edges and every vertex has degree at least three. Find the greatest possible n.
  18. GATE 2016 CS (CS2) Q13 (1 mark, Numerical answer) – Find the minimum number of colours sufficient to vertex-colour every planar graph.
  19. GATE 2016 CS (CS2) Q38 (2 marks, Multiple choice) – There are 23 distinct compounds U. Each of nine compounds in S reacts with exactly three compounds of U. Which always holds? I: Every compound in U∖S…
  20. GATE 2014 CS (CS3) Q61 (2 marks, Multiple choice) – A forest G has n vertices and k connected components. How many edges does it have?
  21. GATE 2014 CS (CS3) Q62 (2 marks, Multiple choice) – Let denote minimum vertex degree. For every planar graph on n vertices with 3, which is TRUE?
  22. GATE 2014 CS (CS2) Q13 (1 mark, Numerical answer) – Find the maximum edges in a bipartite graph on 12 vertices.
  23. GATE 2014 CS (CS2) Q61 (2 marks, Numerical answer) – A cycle on n vertices is isomorphic to its complement. Find n.
  24. GATE 2014 CS (CS1) Q61 (2 marks, Numerical answer) – An undirected graph without self-loops has vertices \(i,j):1 i12,\ 1 j12\. Distinct vertices (a,b) and (c,d) are adjacent when a-c 1 and b-d 1. Find…
  25. GATE 2014 CS (CS1) Q62 (2 marks, Multiple choice) – A nonincreasing n-tuple is graphic if a simple undirected n-vertex graph has those degrees. Which tuple is NOT graphic?
  26. GATE 2017 CS (CS1) Q30 (1 mark, Numerical answer) – Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is .
  27. GATE 2015 CS (CS1) Q44 (2 marks, Numerical answer) – Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is .
  28. GATE 2018 CS Q28 (1 mark, Numerical answer) – The chromatic number of the following graph is .
  29. GATE 2018 CS Q53 (2 marks, Numerical answer) – Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,,100. There is an edge between vertices u…
  30. GATE 2019 CS Q22 (1 mark, Multiple choice) – Let G be an undirected complete graph on n vertices, where n>2. Then the number of different Hamiltonian cycles in G is equal to
  31. GATE 2019 CS Q56 (2 marks, Numerical answer) – Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and…
  32. GATE 2026 CS (CS2) Q36 (2 marks, Multiple choice) – Consider a complete graph K n with n>4 vertices. Each spanning tree of K n is represented as a set of edges. The Jaccard coefficient between two sets…
  33. GATE 2026 CS (CS1) Q55 (2 marks, Multiple select) – An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists a function c: V \0, 1\ such that for every (u, v) E, c(u)…
  34. GATE 2024 CS (CS2) Q17 (1 mark, Multiple choice) – Let A be the adjacency matrix of a simple undirected graph G. Suppose A is its own inverse. Which one of the following statements is always TRUE?
  35. GATE 2024 CS (CS2) Q51 (2 marks, Multiple select) – Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even weight. Which…
  36. GATE 2024 CS (CS2) Q60 (2 marks, Numerical answer) – The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph…
  37. GATE 2024 CS (CS1) Q34 (1 mark, Numerical answer) – The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is
  38. GATE 2024 CS (CS1) Q51 (2 marks, Multiple select) – The 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 vertices and…
  39. GATE 2023 CS Q55 (2 marks, Multiple select) – Let 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, \ denote the set of…
  40. GATE 2022 CS Q30 (1 mark, Numerical answer) – Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .
  41. GATE 2022 CS Q37 (2 marks, Multiple choice) – Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in…
  42. GATE 2022 CS Q50 (2 marks, Multiple select) – The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE?
  43. GATE 2022 CS Q52 (2 marks, Multiple select) – Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
  44. GATE 2022 CS Q58 (2 marks, Numerical answer) – Let G(V,E) be a directed graph, where V=\1,2,3,4,5\ is the set of vertices and E is the set of directed edges, as defined by the following adjacency…
  45. GATE 2021 CS (CS1) Q26 (1 mark, Numerical answer) – In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is .
  46. GATE 2020 CS Q62 (2 marks, Numerical answer) – 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…