Let A be the adjacency matrix of a simple undirected graph G. Suppose A is its own inverse. Which one of the following s...

Question

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?

A. G is a cycle
B. G is a perfect matching
C. G is a complete graph
D. There is no such graph G

Accepted Answer

B. G is a perfect matching If A = A^(-1) then A^2 = I, the identity matrix. The diagonal entries of A^2 equal 1, meaning each vertex has exactly one closed walk of length 2 — i.e., each vertex has exactly one neighbour. Off-diagonal entries of A^2 are 0, meaning no two vertices share a common neighbour. These two conditions together mean G is a disjoint union of edges, which is precisely a perfect matching (assuming n is even). Cycles, complete graphs, and other structures do not satisfy A^2 = I.

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? A. G is a cycle B. G is a perfect matching C. G is a complete graph D. There is no such graph G