GATE CS 2022 (Forenoon) — Question 52

Discrete MathematicsGraph Theory (Connectivity, Paths, Cycles, Trees)MSQ2 marksMedium

Which of the properties hold for the adjacency matrix \(A\) of a simple undirected unweighted graph having \(n\) vertices?
  1. A
    The diagonal entries of \(A^2\) are the degrees of the vertices of the graph.
  2. B
    If the graph is connected, then none of the entries of \(A^{n-1} + I_n\) can be zero.
  3. C
    If the sum of all the elements of \(A\) is at most \(2(n - 1)\), then the graph must be acyclic.
  4. D
    If there is at least a 1 in each of \(A\)'s rows and columns, then the graph must be connected.
Practise the full 2022-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Graph Theory (Connectivity, Paths, Cycles, Trees)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group