Let 𝐴 be the adjacency matrix of a simple undirected graph 𝐺. Suppose 𝐴 is…

Correct answer: The graph is a perfect matching.

Reasoning:

• Since A is its own inverse, A^2 = I (the identity matrix).

• For a simple graph, the diagonal entry (A^2)_{ii} equals the number of length-2 walks from vertex i back to itself, which equals the degree of vertex i.

• Because A^2 = I, each diagonal entry is 1, so every vertex has degree 1.

• A graph in which every vertex has degree 1 is a disjoint union of edges, i.e., a perfect matching. This also implies the number of vertices is even.

• Conversely, the adjacency matrix of a single edge is the 2×2 matrix [[0,1],[1,0]], which squares to the 2×2 identity. A disjoint union of such edges gives a block-diagonal adjacency matrix whose square is the identity, so these graphs do satisfy A = A^{-1}.

• Therefore the only simple graphs with A = A^{-1} are perfect matchings (disjoint unions of edges).