The GATE Grind

GATE 2024 CS (CS2) – Question 17

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Multiple choice

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?

  1. $G$ is a cycle
  2. $G$ is a perfect matching
  3. $G$ is a complete graph
  4. There is no such graph $G$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $G$ is a perfect matching

Explanation

A² = I means each vertex has degree 1 (diagonal of A² is the degree) and off-diagonals vanish, so every vertex has exactly one neighbour: a perfect matching.