Question

In a simple graph, which of the following statements is/are true?
(I) Adjacency matrix is symmetric.
(II) Trace of the adjacency matrix is 1.

• A. Only (I)
• B. Only (II)
• C. Both (I) and (II)
• D. Neither (I) nor (II)

Hint:

Simple graphs have no self-loops, so the adjacency matrix diagonal, and hence its trace, is always zero.

Answer 1

The Correct Option is A

Step 1: A simple graph has no loops (no edges from a vertex to itself) and no multiple edges between the same pair of vertices. Its adjacency matrix \(A\) is defined by \(A_{ij} = 1\) if vertices \(i\) and \(j\) are adjacent, and \(A_{ij} = 0\) otherwise.

Step 2: Check statement (I). Since the graph is undirected, an edge between \(i\) and \(j\) is the same as an edge between \(j\) and \(i\), so \(A_{ij} = A_{ji}\) for all \(i, j\). This means \(A = A^T\), so the adjacency matrix is always symmetric. Statement (I) is true.

Step 3: Check statement (II). Because a simple graph has no loops, every diagonal entry \(A_{ii} = 0\). The trace is the sum of the diagonal entries:

\[ \text{trace}(A) = \sum_{i} A_{ii} = 0 \]

So the trace of the adjacency matrix of a simple graph is always \(0\), never \(1\). Statement (II) is false.

Only statement (I) is true.

\[\boxed{\text{Only (I)}}\]