Discrete Math Quiz: Graph Representations

20 questions · exam conditions

0:00

Graph RepresentationsQuestion 1 of 20

When converting from an adjacency list to an adjacency matrix for a graph with $n$ vertices, which statement about space complexity is most accurate?

Adjacency matrix always uses

O(n^2)

space while adjacency list uses

O(n + m)

where

m

is edges

For dense graphs where

m \approx n^2

, adjacency lists become more space-efficient than matrices

Both representations use identical space when the graph has exactly

n

edges total

Adjacency matrix space complexity depends on the number of edges, not vertices

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Graph Representations

Practice Graph Representations in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Graph Representations, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

When converting from an adjacency list to an adjacency matrix for a graph with $n$ vertices, which statement about space complexity is most accurate?

Adjacency matrix always uses $O(n^2)$ space while adjacency list uses $O(n + m)$ where $m$ is edges (correct answer)
For dense graphs where $m \approx n^2$ , adjacency lists become more space-efficient than matrices
Both representations use identical space when the graph has exactly $n$ edges total
Adjacency matrix space complexity depends on the number of edges, not vertices

Explanation: An adjacency matrix for

n

vertices always requires

O(n^2)

space regardless of edge count, since it must store an

n \times n

matrix. An adjacency list uses

O(n + m)

space:

O(n)

for the vertex array and

O(m)

for storing all edges. For dense graphs (

m \approx n^2

), matrices become more efficient, and for sparse graphs, lists are better.

Question 2

An adjacency list representation uses arrays where each vertex $v$ maps to a sorted array of its neighbors. If vertex 1 maps to $[2, 4, 5]$ , vertex 2 maps to $[1, 3]$ , vertex 3 maps to $[2, 5]$ , vertex 4 maps to $[1]$ , and vertex 5 maps to $[1, 3]$ , what is the value of entry $(2,4)$ in the corresponding adjacency matrix?

0 (correct answer)
1
2
The entry is undefined

Explanation: Entry

(2,4)

is 1 if there's an edge from vertex 2 to vertex 4, and 0 otherwise. Vertex 2's adjacency list is

[1, 3]

, which doesn't contain vertex 4, so there's no edge from 2 to 4. Therefore

(2,4) = 0

. Choice B incorrectly assumes an edge exists. Choice C might confuse matrix arithmetic. Choice D incorrectly suggests the matrix entry doesn't exist.

Question 3

A graph's adjacency matrix $A$ has the property that $A_{i,j} = 1$ if and only if vertices $i$ and $j$ are connected by an edge, and $A_{i,i} = 0$ for all $i$ . If the sum of row 3 is 4 and the sum of column 3 is 2, what can be concluded about the graph?

The graph is undirected with vertex 3 having degree 4
The graph is directed with vertex 3 having out-degree 4 and in-degree 2 (correct answer)
The graph is undirected with vertex 3 having degree 2
The graph has 6 edges incident to vertex 3

Explanation: Since row sums and column sums differ, the matrix is not symmetric, indicating a directed graph. Row sum gives out-degree (edges leaving vertex 3) and column sum gives in-degree (edges entering vertex 3). Choice A assumes undirected but row≠column sum contradicts this. Choice C uses wrong sum. Choice D incorrectly adds in-degree and out-degree.

Question 4

An undirected graph on 5 vertices has the adjacency list representation: $v_1: [v_2, v_4, v_5]$ , $v_2: [v_1, v_3, v_5]$ , $v_3: [v_2, v_4]$ , $v_4: [v_1, v_3]$ , $v_5: [v_1, v_2]$ . How many 1's appear in the upper triangular portion (above the main diagonal) of its adjacency matrix?

4
5 (correct answer)
8
10

Explanation: The edges are: (v₁,v₂), (v₁,v₄), (v₁,v₅), (v₂,v₃), (v₂,v₅), (v₃,v₄). In the upper triangular portion, we count each edge once: positions (1,2), (1,4), (1,5), (2,3), (2,5) give 5 ones. Choice A misses one edge. Choice C counts the full symmetric matrix. Choice D counts each adjacency list entry.

Question 5

A weighted directed graph uses an adjacency matrix where $A_{i,j}$ stores the weight of edge $(i,j)$ if the edge exists, and $\infty$ if no edge exists. The matrix has finite entries at positions $(1,2):5$ , $(1,3):2$ , $(2,3):1$ , $(3,1):4$ , and $\infty$ elsewhere. How would vertex 2's adjacency list be represented using (neighbor, weight) pairs?

$[(1, \infty), (3, 1)]$
$[(3, 1), (1, 4)]$
$[(1, 5), (3, 1)]$
$[(3, 1)]$ (correct answer)

Explanation: When working with graph representations, you need to understand the fundamental difference between adjacency matrices and adjacency lists. An adjacency matrix uses rows to represent source vertices and columns to represent destination vertices, while an adjacency list for a vertex contains only the vertices that can be directly reached from that vertex. To find vertex 2's adjacency list, you need to examine row 2 of the adjacency matrix, which tells you all edges originating from vertex 2. Looking at row 2:

A_{2,1} = \infty

A_{2,2} = \infty

, and

A_{2,3} = 1

. Since only

A_{2,3}

has a finite value, vertex 2 has exactly one outgoing edge: to vertex 3 with weight 1. Therefore, vertex 2's adjacency list is

[(3, 1)]

, making D correct. Choice A is wrong because it includes

(1, \infty)

, suggesting an edge from vertex 2 to vertex 1 that doesn't exist. Choice B incorrectly includes

(1, 4)

, which represents the edge from vertex 3 to vertex 1 (found at position

(3,1)

in the matrix), not an edge from vertex 2. Choice C includes

(1, 5)

, which corresponds to the edge from vertex 1 to vertex 2 (position

(1,2)

), but adjacency lists only show outgoing edges from the specified vertex. Remember: when converting from an adjacency matrix to adjacency lists, always focus on the row corresponding to your vertex of interest. The row index represents the source vertex, and finite entries in that row indicate the destinations and weights of outgoing edges.

Question 6

Consider the adjacency list representation where vertex $A$ maps to $[B, C, D]$ , vertex $B$ maps to $[A, D]$ , vertex $C$ maps to $[A]$ , and vertex $D$ maps to $[A, B, E]$ , but vertex $E$ is missing from the representation. What should vertex $E$ 's adjacency list be to make this a valid undirected graph?

$[A, B, C, D]$
$[]$ (empty list)
$[A, D]$
$[D]$ (correct answer)

Explanation: When working with adjacency lists for undirected graphs, remember that adjacency must be symmetric: if vertex

X

is adjacent to vertex

Y

, then

Y

must also be adjacent to

X

. This bidirectional property is what makes the graph "undirected." To find

E

's adjacency list, examine which vertices claim to be adjacent to

E

. Looking at the given adjacency lists, only vertex

D

includes

E

in its list:

[A, B, E]

. Since

D

is adjacent to

E

, the symmetry property requires that

E

must be adjacent to

D

. No other vertex mentions

E

, so

E

is only connected to

D

. Therefore,

E

's adjacency list should be

[D]

, making answer D correct. Let's see why the other options violate the symmetry requirement: A)

[A, B, C, D]

would mean

E

is adjacent to all other vertices, but none of

A

B

, or

C

include

E

in their lists. This creates asymmetric connections. B)

[]

(empty list) would mean

E

has no neighbors, but

D

claims to be adjacent to

E

. This breaks the symmetry between

D

and

E

. C)

[A, D]

includes

A

, but

A

's list

[B, C, D]

doesn't include

E

, creating another asymmetric relationship. Study tip: When checking adjacency lists for undirected graphs, always verify that every connection appears in both directions. Scan each vertex's list and ensure the reverse connection exists.

Question 7

A complete bipartite graph $K_{3,4}$ has vertex sets $U = \{u_1, u_2, u_3\}$ and $V = \{v_1, v_2, v_3, v_4\}$ where every vertex in $U$ connects to every vertex in $V$ . In the adjacency list representation, what is the total length of all adjacency lists combined?

12
14
24 (correct answer)
28

Explanation: Each vertex in

U

connects to 4 vertices in

V

, and each vertex in

V

connects to 3 vertices in

U

. Total list length =

3 \times 4 + 4 \times 3 = 12 + 12 = 24

. Choice A counts only edges once. Choice B adds vertices to edge count. Choice D incorrectly computes

7 \times 4

Question 8

A directed graph has vertices $\{v_1, v_2, v_3, v_4\}$ and edges $\{(v_1, v_2), (v_1, v_3), (v_2, v_4), (v_3, v_1), (v_3, v_4), (v_4, v_3)\}$ . What is the sum of all entries in the adjacency matrix representation of this graph?

6 (correct answer)
8
10
12

Explanation: The adjacency matrix has a 1 for each directed edge and 0 elsewhere. Since there are exactly 6 directed edges listed, the sum of all entries equals 6. Choice B incorrectly counts vertices plus edges. Choice C might result from double-counting bidirectional connections. Choice D incorrectly counts each edge twice.

Question 9

A graph's adjacency matrix has all zero entries on the main diagonal. After adding a self-loop to vertex 3, exactly one entry changes from 0 to 1. If the original matrix was symmetric, which property is preserved after adding the self-loop?

The matrix remains symmetric and represents an undirected graph (correct answer)
The matrix becomes asymmetric but still represents an undirected graph
The matrix remains symmetric but now represents a directed graph
The row sums equal the column sums for all vertices

Explanation: Adding a self-loop changes only the diagonal entry

(3,3)

from 0 to 1. Since diagonal entries equal their own transposes, the matrix remains symmetric. A symmetric adjacency matrix with self-loops still represents an undirected graph (now with self-loops allowed). Choices B and C incorrectly claim the graph type changes. Choice D is true but not the most specific preserved property.

Question 10

An adjacency matrix $A$ for an undirected graph satisfies $A^2_{i,j} = \text{number of paths of length 2 from vertex } i \text{ to vertex } j$ . If $A$ has 1's at positions $(1,2)$ , $(1,3)$ , $(2,1)$ , $(2,4)$ , $(3,1)$ , $(4,2)$ and 0's elsewhere, what is $A^2_{1,4}$ ?

0
1 (correct answer)
2
3

Explanation:

A^2_{1,4} = \sum_{k} A_{1,k} \cdot A_{k,4}

. From the given entries:

A_{1,2} = A_{1,3} = 1

, others in row 1 are 0. Only

A_{2,4} = 1

in column 4, others are 0. So

A^2_{1,4} = A_{1,2} \cdot A_{2,4} = 1 \cdot 1 = 1

. There's exactly one path of length 2 from vertex 1 to vertex 4:

1 \to 2 \to 4

. Other choices miscount the matrix multiplication.

Question 11

Consider an undirected multigraph (allowing multiple edges between the same pair of vertices) with adjacency matrix $A$ where $A_{i,j}$ equals the number of edges between vertices $i$ and $j$ . If converting to an adjacency list representation where each edge is listed separately, and vertex 3 has matrix row $[0, 2, 0, 1, 3]$ , how many entries will appear in vertex 3's adjacency list?

3 entries: vertices 2, 4, and 5
4 entries: two 2's, one 4, and three 5's
6 entries: 2, 2, 4, 5, 5, 5 (correct answer)
12 entries accounting for bidirectional representation

Explanation: In a multigraph adjacency list, each edge is listed separately. Row

[0, 2, 0, 1, 3]

means 0 edges to vertex 1, 2 edges to vertex 2, 0 edges to vertex 3, 1 edge to vertex 4, and 3 edges to vertex 5. The adjacency list contains: 2, 2, 4, 5, 5, 5 (total 6 entries). Choice A counts unique neighbors only. Choice B misinterprets the format. Choice D double-counts for undirected edges.

Question 12

Consider converting between representations of a graph with $n$ vertices and $m$ edges. The adjacency matrix requires $\Theta(n^2)$ space, while adjacency lists require $\Theta(n + m)$ space. For which type of graph do these space complexities become equal in order of magnitude?

When the graph is sparse with $m = O(\log n)$
When the graph is a tree with $m = n - 1$
When the graph is moderately dense with $m = \Theta(n)$
When the graph is dense with $m = \Theta(n^2)$ (correct answer)

Explanation: When analyzing graph representation space complexities, you need to determine when

\Theta(n^2)

and

\Theta(n + m)

represent the same order of magnitude. This happens when the dominant terms in both expressions are equal. For adjacency lists with

\Theta(n + m)

space to equal adjacency matrix's

\Theta(n^2)

space, the

m

term must dominate the

n

term in the first expression. This occurs when

m = \Theta(n^2)

, making the adjacency list space

\Theta(n + n^2) = \Theta(n^2)

. Answer D correctly identifies this scenario: when the graph is dense with

m = \Theta(n^2)

, both representations require

\Theta(n^2)

space. Answer A is wrong because when

m = O(\log n)

, adjacency lists need only

\Theta(n + \log n) = \Theta(n)

space, which is much less than

\Theta(n^2)

for large

n

. Answer B is incorrect because trees have

m = n - 1

, so adjacency lists require

\Theta(n + (n-1)) = \Theta(n)

space, again much smaller than

\Theta(n^2)

. Answer C fails because when

m = \Theta(n)

, adjacency lists need

\Theta(n + n) = \Theta(n)

space, which remains significantly less than the matrix's

\Theta(n^2)

requirement. Study tip: Remember that space complexities are equal only when both expressions have the same dominant term. For graph representations, this happens precisely when the number of edges reaches

\Theta(n^2)

— the maximum possible for simple graphs.

Question 13

A bipartite graph with vertex sets $X = \{x_1, x_2, x_3\}$ and $Y = \{y_1, y_2\}$ has edges from each $x_i$ to every vertex in $Y$ . If the vertices are ordered as $x_1, x_2, x_3, y_1, y_2$ in the adjacency matrix, which pattern appears?

A $5 \times 5$ matrix with 1s only in positions where both indices are from the same partition
A $5 \times 5$ matrix with 1s in the upper-right $3 \times 2$ and lower-left $2 \times 3$ blocks (correct answer)
A $5 \times 5$ matrix with 1s forming a checkerboard pattern throughout
A $5 \times 5$ matrix with 1s only in the main diagonal and super-diagonal positions

Explanation: In a bipartite graph, edges only exist between vertices in different partitions. With ordering

x_1, x_2, x_3, y_1, y_2

, edges from

X

Y

create 1s in the upper-right

3 \times 2

block (rows 1-3, columns 4-5). Since the graph is undirected, edges from

Y

X

create 1s in the lower-left

2 \times 3

block (rows 4-5, columns 1-3). All other entries are 0.

Question 14

A programmer incorrectly implements an adjacency list by including each undirected edge only once (instead of twice) in the data structure. When this flawed adjacency list is converted back to an adjacency matrix, what property will the resulting matrix definitely have?

The matrix will have exactly half the number of 1s as the correct adjacency matrix
The matrix will be identical to the correct matrix since conversion algorithms compensate automatically
The matrix will have all 1s above the main diagonal and all 0s below it
The matrix will be asymmetric with some entries $a_{ij} \neq a_{ji}$ where edges exist (correct answer)

Explanation: When dealing with graph representations, understanding how adjacency lists and matrices correspond is crucial. In a correct undirected graph implementation, each edge appears twice in the adjacency list: if there's an edge between vertices i and j, then j appears in i's list AND i appears in j's list. The flawed implementation only stores each edge once, meaning some edges will be "one-way" in the adjacency list. When you convert this back to an adjacency matrix, you'll set

a_{ij} = 1

if j appears in vertex i's list, but if the edge was only stored once (say, only j in i's list but not i in j's list), then

a_{ji} = 0

. This creates asymmetry where

a_{ij} \neq a_{ji}

for existing edges, making answer D correct. Answer A is wrong because the number of 1s depends on exactly how edges were stored, not necessarily half. Answer B is incorrect since standard conversion algorithms don't automatically compensate for missing entries—they convert what's actually in the data structure. Answer C assumes a very specific storage pattern (upper triangular) that wasn't specified; the programmer could have stored edges inconsistently in any direction. Study tip: Remember that undirected graphs require symmetric adjacency matrices (

a_{ij} = a_{ji}

) and symmetric adjacency lists (mutual references). When you see questions about flawed graph implementations, check whether the fundamental symmetry property is violated—this is often the key insight being tested.

Question 15

Consider the adjacency list representation: vertex 1: [2, 3], vertex 2: [1, 4], vertex 3: [1, 4], vertex 4: [2, 3, 5], vertex 5: [4]. In the corresponding adjacency matrix, how many entries are equal to 1?

8 entries equal to 1
9 entries equal to 1
10 entries equal to 1 (correct answer)
11 entries equal to 1

Explanation: Each entry in an adjacency list corresponds to a 1 in the adjacency matrix. Counting all list entries: vertex 1 has 2 entries, vertex 2 has 2 entries, vertex 3 has 2 entries, vertex 4 has 3 entries, vertex 5 has 1 entry. Total:

2+2+2+3+1 = 10

entries, so exactly 10 matrix entries equal 1.

Question 16

Consider a directed graph where vertex 3's adjacency list is [1, 4, 1, 2]. When constructing the adjacency matrix representation, what constraint must be satisfied for this to be a valid simple directed graph?

The adjacency matrix must be symmetric with all diagonal entries equal to zero
All entries in row 3 must be either 0 or 1, with at most one 1 per column
The adjacency matrix cannot have this representation since simple graphs forbid multiple edges (correct answer)
Row 3 must sum to exactly 4 and all entries must be non-negative integers

Explanation: The adjacency list [1, 4, 1, 2] for vertex 3 indicates edges to vertices 1, 4, 1, and 2. Since vertex 1 appears twice, this represents multiple edges from vertex 3 to vertex 1. Simple graphs do not allow multiple edges between vertices, so this adjacency list cannot represent a simple directed graph. It could only represent a multigraph.

Question 17

Two different adjacency list representations of the same undirected graph are given: List A has vertex 3: [1, 2, 4] and List B has vertex 3: [4, 1, 2]. When converted to adjacency matrices using identical vertex orderings, how do the resulting matrices compare?

The matrices cannot be compared without knowing the complete adjacency list representation
The matrices will differ in row 3 but be identical in all other rows and columns
The matrices will be transposes of each other due to the different list orderings
The matrices will be identical since adjacency lists order is irrelevant for undirected graphs (correct answer)

Explanation: When you encounter questions about graph representations, remember that different representations of the same graph must capture identical structural information, regardless of how that information is organized or ordered. An adjacency list for an undirected graph simply records which vertices are connected to each vertex. For vertex 3, both List A [1, 2, 4] and List B [4, 1, 2] tell you the exact same thing: vertex 3 is connected to vertices 1, 2, and 4. The order in which these neighbors are listed is completely arbitrary and doesn't affect the underlying graph structure. When you convert either list to an adjacency matrix using the same vertex ordering, you're creating a matrix where entry (i,j) equals 1 if vertices i and j are connected, and 0 otherwise. Since both lists contain identical connection information for vertex 3, row 3 of both matrices will be identical. The same logic applies to all other vertices, making the complete matrices identical. Option A is wrong because the connection information for vertex 3 is complete in both representations. Option B incorrectly assumes that different list orderings create different matrix entries, but matrix entries depend only on whether connections exist, not on list order. Option C misunderstands how adjacency matrices work—the order within adjacency lists doesn't affect matrix structure, and undirected graphs always produce symmetric (not just transposed) matrices anyway. Remember: adjacency lists are like shopping lists—whether you write "milk, eggs, bread" or "bread, milk, eggs," you're buying the same items. The order doesn't change the underlying relationships.

Question 18

A graph $G$ has the adjacency matrix $$A = \begin{pmatrix} 0 & 1 & 0 & 1 \ 1 & 0 & 2 & 0 \ 0 & 2 & 0 & 1 \ 1 & 0 & 1 & 0 \end{pmatrix}

8 entries total
10 entries total (correct answer)
12 entries total
14 entries total

Explanation: In the adjacency matrix, we count all non-zero entries: positions (0,1)=1, (0,3)=1, (1,0)=1, (1,2)=2, (2,1)=2, (2,3)=1, (3,0)=1, (3,2)=1. For adjacency lists, each non-zero entry

a_{ij}

with value

k

contributes

k

entries to vertex

i

's list. So vertex 0 has 2 entries, vertex 1 has 3 entries (1+2), vertex 2 has 3 entries (2+1), and vertex 3 has 2 entries, totaling 10 entries.

Question 19

An undirected graph has adjacency lists: vertex A: [B, C, D], vertex B: [A, D], vertex C: [A], vertex D: [A, B, E], vertex E: [D]. If we construct the adjacency matrix with vertices ordered alphabetically, what is the sum of all entries in the matrix?

10 (correct answer)
12
14
16

Explanation: For an undirected graph, each edge contributes 2 to the sum of the adjacency matrix (once for each direction). From the adjacency lists, the edges are: A-B, A-C, A-D, B-D, D-E. That's 5 edges total. Since each edge appears twice in an undirected graph's adjacency matrix (as

a_{ij} = a_{ji} = 1

), the sum is

5 \times 2 = 10

Question 20

A graph's adjacency matrix has exactly 3 ones in row 2 and exactly 2 ones in column 2. What can be definitively concluded about the graph?

The graph must be directed since the in-degree and out-degree of vertex 2 differ (correct answer)
The graph must be undirected since adjacency matrices require symmetry for valid representations
Vertex 2 has degree 5 regardless of whether the graph is directed or undirected
The graph representation is invalid since row and column sums must be equal

Explanation: In an undirected graph, the adjacency matrix must be symmetric, so entry

a_{ij} = a_{ji}

. This means row 2 and column 2 would have the same sum. Since row 2 has sum 3 and column 2 has sum 2, the matrix cannot be symmetric, so the graph must be directed. The out-degree of vertex 2 is 3 and the in-degree is 2.