Questions: Graph Representation: Adjacency and Incidence Matrices

Question 1

For a graph G with adjacency matrix A, the entry (A²)[i][j] = 3. What does this tell you about the graph?

• A. There are 3 edges directly connecting vertex i to vertex j
• B. There are 3 distinct walks of length exactly 2 from vertex i to vertex j — meaning 3 different intermediate vertices k such that edges i→k and k→j both exist
• C. Vertex i and vertex j are 3 hops apart in the shortest path
• D. There are 3 triangles (3-cycles) in the graph that include both vertex i and vertex j

Answer: (B)

Matrix multiplication encodes path counting. The entry (A²)[i][j] = Σ_k A[i][k] × A[k][j] counts the number of intermediate vertices k where both A[i][k] = 1 and A[k][j] = 1 — i.e., the number of length-2 walks from i to j. A value of 3 means there are exactly 3 such intermediate vertices. This is not the shortest-path distance (that would require different algorithms like BFS), and it counts walks, not paths — if any of those 3 walks revisit vertices, they still count. This connection between linear algebra and graph structure is the key insight of the adjacency matrix representation.

Question 2

For which type of graph is an adjacency list representation generally preferred over an adjacency matrix, and why?

• A. Dense graphs, because adjacency lists enumerate all edges explicitly while matrices require index lookups
• B. Small graphs, because adjacency lists fit in a single array while matrix construction is computationally expensive
• C. Sparse graphs, because the adjacency matrix is mostly zeros and wastes O(n²) space to represent O(n) or O(m) edges
• D. Directed graphs, because adjacency lists naturally represent asymmetric relationships while matrices require separate row/column logic

Answer: (C)

An adjacency matrix for an n-vertex graph always requires O(n²) space regardless of the number of edges. For a sparse graph — one with far fewer edges than n² — the matrix is mostly zeros and this space is wasted. An adjacency list represents only the edges that actually exist, using O(n + m) space where m is the number of edges. For a sparse graph where m << n², the adjacency list is dramatically more efficient. For a dense graph (m close to n²), the matrix is more appropriate, especially since it enables fast edge-existence queries (O(1) vs. O(degree) for lists) and leverages linear algebra tools like matrix multiplication and eigendecomposition.

Question 3

The adjacency matrix of an undirected graph is always symmetric because every edge {i, j} contributes entries in both A[i][j] and A[j][i].

• T. True
• F. False

Answer: True

In an undirected graph, an edge between vertices i and j means you can traverse it in either direction. The adjacency matrix represents this by setting both A[i][j] = 1 and A[j][i] = 1. Since this is true for every edge, the resulting matrix satisfies A = Aᵀ — the definition of a symmetric matrix. This symmetry is not a coincidence but a direct encoding of the undirected nature of the edges. For directed graphs, an edge i → j only contributes A[i][j] = 1, with no automatic reciprocal, so the matrix need not be symmetric.

Question 4

If A[i][j] = 1 in the adjacency matrix of a directed graph, then A[j][i] should also equal 1.

• T. True
• F. False

Answer: False

In a directed graph (digraph), A[i][j] = 1 means there is a directed edge from vertex i to vertex j. This says nothing about whether there is an edge from j back to i. A[j][i] = 1 would require a separate directed edge j → i to exist. The adjacency matrix of a directed graph is therefore not necessarily symmetric. This asymmetry is precisely what makes the directed/undirected distinction matter in the matrix representation: symmetry is a property of the undirected case, not a general property of adjacency matrices.

Question 5

Explain what information is encoded in the matrix A² (A squared), and describe why this result connects matrix algebra to graph reachability.

Model answer: A² is computed by the standard matrix product: (A²)[i][j] = Σ_k A[i][k] × A[k][j]. Because A[i][k] and A[k][j] are each 0 or 1 (for a simple graph), their product is 1 only when both edges exist — i.e., when k is an intermediate vertex with edges from i to k and from k to j. Summing over all k therefore counts the number of length-2 walks from i to j. More generally, (Aᵏ)[i][j] counts all walks of exactly length k from i to j. This connects to reachability: if any entry of A + A² + ... + Aⁿ⁻¹ is positive for all (i,j) pairs, the graph is strongly connected — every vertex can reach every other within at most n-1 steps. The matrix representation thus allows questions about graph structure (connectivity, path counting) to be answered using the toolkit of linear algebra.

This connection is the foundation of spectral graph theory: the eigenvalues and eigenvectors of the adjacency matrix encode deep structural properties of the graph — including connectivity, bipartiteness, and expansion. Matrix multiplication is just the entry point into this much richer relationship.