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 \)

Hint:

When the adjacency matrix of a graph satisfies \( A \cdot A = I \), the graph represents a perfect matching.

Answer 1

The Correct Option is B

If \( A \) is the adjacency matrix of an undirected graph \( G \), and \( A \cdot A = I \) (where \( I \) is the identity matrix), it means that the graph \( G \) satisfies the following conditions: 1. Each node in \( G \) is connected to exactly one other node because \( A \cdot A = I \) implies no node connects back to itself (diagonal is 1 in \( I \)). 2. There are no paths of length 2 between any two nodes in \( G \). This describes a perfect matching, where each node is paired with exactly one other node. Step 1: Analyze other options. (A) \( G \) is a cycle: A cycle would not satisfy \( A \cdot A = I \) because there are paths of length 2. (C) \( G \) is a complete graph: A complete graph does not satisfy \( A \cdot A = I \) because all nodes are connected. (D) There is no such graph \( G \): This is incorrect because graphs with perfect matchings exist. Final Answer: \[ \boxed{\text{Perfect Matching}} \]