Which of the properties hold for the adjacency matrix A of a simple undirected…

Answer: Only the statement that the diagonal entries of A^2 are the degrees of the vertices is correct.

• The diagonal entries of A^2 are the degrees of the vertices. Reason: (A^2)_{ii} = sum_j A_{ij}A_{ji} = sum_j A_{ij}, and since A is symmetric for an undirected simple graph this sum equals the degree of vertex i.

• The claim that if the graph is connected then none of the entries of A^{n-1}+I_n can be zero is false. Reason: Entries of A^k count walks of length k, but there may be no walk of exactly length n-1 between some vertices (for example because of parity constraints). Concrete counterexample: the path on 3 vertices (1–2–3) has n=3; for its adjacency matrix A one finds A^{2}+I has zero entries off the diagonal, so some entries can be zero.

• The claim that if the sum of all elements of A is at most 2(n−1) then the graph must be acyclic is false. Reason: The sum of entries of A equals 2E where E is the number of edges, so the condition is E ≤ n−1. While an acyclic graph (forest) satisfies E ≤ n−1, having E ≤ n−1 does not force the graph to be acyclic: for example a triangle (3-cycle) together with an isolated vertex gives n=4 and E=3 ≤ 3, yet the graph contains a cycle.

• The claim that if there is at least a 1 in each of A’s rows and columns then the graph must be connected is false. Reason: Requiring at least one 1 per row/column only excludes isolated vertices (every vertex has degree ≥ 1), but the graph can still split into multiple components each with minimum degree ≥ 1. Example: two disjoint edges on four vertices (edges 1–2 and 3–4) satisfy the row/column condition but the graph is disconnected.

Summary: Only the statement identifying diagonal entries of A^2 with vertex degrees is correct; the other three statements are false with the given counterexamples.