Correct : b

To find which statement is always true when the adjacency matrix A of a simple undirected graph G is its own inverse, let us analyze the mathematical implications step-by-step.
1. Understand the Matrix Properties: • Since A is its own inverse, we have:
    A · A = I → A² = I (where I is the Identity Matrix)
• Since G is a simple undirected graph, its adjacency matrix A has two specific traits:
    1. It is symmetric (A = A^T).
    2. Its diagonal elements are all zero (A_ii = 0 for all i), because a simple graph has no self-loops.
2. Analyze the Matrix Multiplication (A²): Let's look at what an individual diagonal entry in the matrix A² represents. By definition of matrix multiplication:
    (A²)_ii = ∑_j=1ⁿ A_ij · A_ji

Since A is symmetric (A_ij = A_ji), this simplifies to:
    (A²)_ii = ∑_j=1ⁿ (A_ij)²

In an adjacency matrix, A_ij is either 1 (if an edge exists between vertex i and vertex j) or 0 (if no edge exists). Therefore, (A_ij)² = A_ij. This means:
    (A²)_ii = ∑_j=1ⁿ A_ij = Degree of vertex i

Since we are given that A² = I, every diagonal element of A² must equal 1 (the diagonal entries of the identity matrix):
    Degree of vertex i = 1 (for every vertex i in the graph G)
3. Interpret the Structural Layout of G: • If every single vertex in an undirected graph has a degree of exactly 1, the graph must be a collection of disjoint edges.
• Since every vertex has exactly one edge incident upon it, all vertices are perfectly paired up into independent edges.
• A graph where every vertex is incident on exactly one edge forms a perfect matching (or a 1-regular graph made of disconnected copies of K₂).
Conclusion: Graph G must be a perfect matching, which matches option (b).