GATE CS 2024 Set 2 Q.17: Graph Theory

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?

$G$ is a cycle

$G$ is a perfect matching

$G$ is a complete graph

There is no such graph $G$

Official answer and solution

Official answer: B
From: Official GATE 2024 answer key

Solution

Use the property that the $i$ -th diagonal entry of $A^2$ equals the degree of vertex $i$ in a simple undirected graph.

For any simple undirected graph $G$ , the adjacency matrix $A$ is symmetric with $(A^2)_{ii} = \sum_{k} A_{ik}^2 = \deg(v_i)$ , the degree of vertex $v_i$ .

Since $A$ is its own inverse, $A^2 = I$ (the identity matrix). Equating the diagonal entries gives:

\deg(v_i) = (A^2)_{ii} = I_{ii} = 1 \quad \text{for every vertex } v_i \in V(G)

A simple graph in which every vertex has degree exactly $1$ is a collection of vertex-disjoint edges covering all vertices, i.e., $G$ is a perfect matching.

Final answer

Option (B)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 17 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source