# Graph Theory

 Question 1
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?
MSQ
 A The diagonal entries of $A^2$ are the degrees of the vertices of the graph. B If the graph is connected, then none of the entries of $A^{n-1}+I_n$can be zero. C If the sum of all the elements of $A$ is at most 2(n-1), then the graph must be acyclic. D If there is at least a 1 in each of A's rows and columns, then the graph must be connected.
GATE CSE 2022   Discrete Mathematics
Question 1 Explanation:
 Question 2
The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE?
MSQ
 A The chromatic number of the graph is 3. B The graph has a Hamiltonian path. C The following graph is isomorphic to the Peterson graph.  D The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)
GATE CSE 2022   Discrete Mathematics
Question 2 Explanation:
 Question 3
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 the graph is given by the trace of
 A $A^3$ B $A^3$ divided by 2 C $A^3$ divided by 3 D $A^3$ divided by 6
GATE CSE 2022   Discrete Mathematics
Question 3 Explanation:
 Question 4
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .
 A 72 B 36 C 16 D 48
GATE CSE 2022   Discrete Mathematics
Question 4 Explanation:
 Question 5
In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1. The sum of the quality-scores of all vertices on the graph shown above is ______
 A 929 B 254 C 639 D 879
GATE CSE 2021 SET-2   Discrete Mathematics
Question 5 Explanation:
 Question 6
Consider the following directed graph: Which of the following is/are correct about the graph?
[MSQ]
 A The graph does not have a topological order B A depth-first traversal starting at vertex S classifies three directed edges as back edges C The graph does not have a strongly connected component D For each pair of vertices u and v, there is a directed path from u to v
GATE CSE 2021 SET-2   Discrete Mathematics
Question 6 Explanation:
 Question 7
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.
Which of the following options is/are correct?
 A Root of T can never be an articulation point in G. B Root of T is an articulation point in G if and only if it has 2 or more children. C A leaf of T can be an articulation point in G. D If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
GATE CSE 2021 SET-1   Discrete Mathematics
Question 7 Explanation:
 Question 8
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?
 A v2v4 B v1v4 C v4v5 D v3v4
ISRO CSE 2020   Discrete Mathematics
Question 8 Explanation:
 Question 9
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 _______
 A 4 B 5 C 6 D 7
GATE CSE 2020   Discrete Mathematics
Question 9 Explanation:
 Question 10
Let G be an undirected complete graph on n vertices, where n$\gt$2. Then, the number of different Hamiltonian cycles in G is equal to
 A n! B (n-1)! C 1 D $\frac{(n-1)!}{2}$
GATE CSE 2019   Discrete Mathematics
Question 10 Explanation:

There are 10 questions to complete.

### 5 thoughts on “Graph Theory”

1. Question 6 is of group theory.
Please remove it from here.

• Thank You Abhishek Chavle,
We have updated it.

• Q 11 and 29 too

• 2. 