GATE Engineering Mathematics: Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) – Previous Year Questions
21 GATE previous year questions on Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) (Engineering Mathematics, Computer Science) with answers and explanations, from every paper.
- GATE 2017 CS Q30 – Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is .
- GATE 2015 CS 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. [Figure: the standard Petersen graph on 10 vertices.] Which of the…
- 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 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…