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.
- GATE 2007 CS Q4 – Let G be a nonplanar graph with the minimum possible number of edges. G has
- GATE 2007 CS Q23 – Which graph has an Eulerian circuit?
- GATE 2008 CS Q23 – Which is true for every planar graph on n vertices?
- GATE 2008 CS Q42 – Graph G has n vertices and2n−2 edges partitionable into two edge-disjoint spanning trees. Which is NOT true?
- GATE 2009 CS Q2 – What is the chromatic number of an n-vertex simple connected graph which does not contain any odd-length cycle? Assume n2.
- GATE 2009 CS Q3 – Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
- GATE 2015 CS (CS2) Q61 – A self-complementary graph is isomorphic to its complement. What must its vertex count n satisfy?
- GATE 2015 CS (CS2) Q62 – A bridge is an edge whose removal disconnects a connected graph. Which is true?
- GATE 2010 CS Q11 – 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?
- GATE 2010 CS Q38 – 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
- GATE 2011 CS Q27 – The drawings show complete graph K₄ and cube graph Q₃. Which is true?
- GATE 2013 CS Q35 – For undirected graphs, P: The number of odd-degree vertices is even. Q: The sum of all vertex degrees is even. Which hold?
- GATE 2013 CS Q36 – 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…
- GATE 2012 CS Q27 – A connected simple planar graph has ten vertices and fifteen edges. How many bounded faces does any plane embedding have?
- GATE 2012 CS Q36 – Which graph A,B,C,D is isomorphic to the given graph?
- GATE 2012 CS Q48 – A complete undirected graph has six labelled vertices. How many distinct cycles of length four does it contain?
- GATE 2017 CS (CS2) Q33 – An undirected graph has n vertices, 25 edges and every vertex has degree at least three. Find the greatest possible n.
- GATE 2016 CS (CS2) Q13 – Find the minimum number of colours sufficient to vertex-colour every planar graph.
- GATE 2016 CS (CS2) Q38 – 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…
- GATE 2014 CS (CS3) Q61 – A forest G has n vertices and k connected components. How many edges does it have?
- GATE 2014 CS (CS3) Q62 – Let denote minimum vertex degree. For every planar graph on n vertices with 3, which is TRUE?
- GATE 2014 CS (CS2) Q13 – Find the maximum edges in a bipartite graph on 12 vertices.
- GATE 2014 CS (CS2) Q61 – A cycle on n vertices is isomorphic to its complement. Find n.
- GATE 2014 CS (CS1) Q61 – 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…
- GATE 2014 CS (CS1) Q62 – A nonincreasing n-tuple is graphic if a simple undirected n-vertex graph has those degrees. Which tuple is NOT graphic?
- GATE 2017 CS (CS1) Q30 – Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is .
- GATE 2015 CS (CS1) Q44 – 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 .
- GATE 2018 CS Q28 – The chromatic number of the following graph is .
- GATE 2018 CS Q53 – 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…
- GATE 2019 CS Q22 – 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
- GATE 2019 CS Q56 – 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…
- GATE 2026 CS (CS2) Q36 – 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…
- GATE 2026 CS (CS1) Q55 – 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)…
- GATE 2024 CS (CS2) Q17 – 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?
- GATE 2024 CS (CS2) Q51 – 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…
- GATE 2024 CS (CS2) Q60 – 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…
- GATE 2024 CS (CS1) Q34 – The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is
- GATE 2024 CS (CS1) Q51 – 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…
- GATE 2023 CS Q55 – 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…
- GATE 2022 CS Q30 – Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .
- GATE 2022 CS Q37 – 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…
- GATE 2022 CS Q50 – The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE?
- GATE 2022 CS Q52 – Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
- GATE 2022 CS Q58 – 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…
- GATE 2021 CS (CS1) Q26 – In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is .
- GATE 2020 CS Q62 – 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…