Finite Mathematics Quiz: Network Representations
16 questions · exam conditions
0:00
Network RepresentationsQuestion 1 of 16

A social media network can be represented as a graph where vertices represent users and edges represent mutual followings. If the adjacency matrix of this network has a row sum of 4 for user X and a column sum of 6 for user X, what can we conclude about user X's connections in this directed network?

User X follows 4 people and is followed by 6 people in the network
User X follows 6 people and is followed by 4 people in the network
User X has 10 total bidirectional connections in the network
User X has 4 bidirectional and 2 unidirectional connections in the network
← Back to quizzes

Finite Mathematics Quiz

Finite Mathematics Quiz: Network Representations

Practice Network Representations in Finite Mathematics 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 Network Representations, giving you a quick way to practice the rules, question types, and explanations that matter most for Finite Mathematics.

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

A social media network can be represented as a graph where vertices represent users and edges represent mutual followings. If the adjacency matrix of this network has a row sum of 4 for user X and a column sum of 6 for user X, what can we conclude about user X's connections in this directed network?

  1. User X follows 4 people and is followed by 6 people in the network (correct answer)
  2. User X follows 6 people and is followed by 4 people in the network
  3. User X has 10 total bidirectional connections in the network
  4. User X has 4 bidirectional and 2 unidirectional connections in the network
Explanation: In a directed graph's adjacency matrix, the row sum represents out-degree (who X follows) and the column sum represents in-degree (who follows X). Row sum 4 means X follows 4 people; column sum 6 means 6 people follow X. Choice B reverses the interpretation. Choice C incorrectly adds them as if undirected. Choice D makes assumptions about bidirectional vs unidirectional connections that cannot be determined from just the sums.

Question 2

A network has 6 vertices labeled A through F. The adjacency matrix shows that vertex A is connected to vertices B, C, and E; vertex B is connected to A, D, and F; vertex C is connected to A and D; vertex D is connected to B, C, and F; vertex E is connected to A and F; and vertex F is connected to B, D, and E. If we remove vertex D and all its incident edges from the network, what is the degree of vertex B in the resulting graph?

  1. 1
  2. 2 (correct answer)
  3. 3
  4. 4
Explanation: Initially, vertex B is connected to A, D, and F (degree 3). When vertex D is removed along with all its incident edges, the edge B-D is eliminated. In the resulting graph, vertex B is only connected to A and F, giving it a degree of 2. Choice A represents an error of removing too many connections. Choice C is the original degree before removal. Choice D incorrectly adds connections.

Question 3

A communication network has vertices representing cities and edges representing direct communication links. The network can be represented by the adjacency list: City A: [B, D, E]; City B: [A, C, F]; City C: [B, F]; City D: [A, E]; City E: [A, D, F]; City F: [B, C, E]. If a message must travel from City A to City C using exactly 3 communication hops, how many different paths are possible?

  1. 5 distinct paths through the network
  2. 3 distinct paths through the network
  3. 4 distinct paths through the network
  4. 2 distinct paths through the network (correct answer)
Explanation: When you encounter a graph theory problem asking for paths with a specific number of steps, you need to systematically trace all possible routes while carefully tracking the exact path length required. To find paths from City A to City C using exactly 3 hops, start at A and methodically explore all 3-step routes. From A, you can go to cities B, D, or E (first hop). From each of these, continue for exactly two more hops until you reach C. Let's trace systematically: Starting A → B (hop 1) → A (hop 2) → ? won't work since A doesn't connect directly to C. Try A → B → F → C - this works! Next: A → D → A → ? again fails. Try A → D → E → F, but F doesn't lead to C in zero hops. Continue this process: A → E → D → A fails, but A → E → F → C works! The complete enumeration reveals exactly 2 valid paths: A → B → F → C and A → E → F → C. Both use exactly 3 hops and end at the target. Answer A (5 paths) likely counts paths of different lengths or includes invalid routes. Answer B (3 paths) and Answer C (4 paths) suggest incomplete enumeration - perhaps missing the constraint of exactly 3 hops or double-counting. These errors commonly occur when students don't systematically verify each path's length. The correct answer is D: 2 distinct paths. Study tip: For path-counting problems, always enumerate systematically and verify each path meets all constraints (exact length, start/end points). Drawing the network visually can prevent missed connections or counting errors.

Question 4

A computer network has 6 nodes where each node maintains a connection list. Node A connects to [B,C,E], Node B connects to [A,D,F], Node C connects to [A,D], Node D connects to [B,C,F], Node E connects to [A,F], and Node F connects to [B,D,E]. If the network must remain connected after removing one edge, which edge removal would result in the greatest increase in the shortest path between two specific nodes?

  1. Removing edge A-C increases the shortest path from A to D the most
  2. Removing edge B-D increases the shortest path from A to F the most
  3. Removing edge A-E increases the shortest path from E to C the most (correct answer)
  4. Removing edge D-F increases the shortest path from B to E the most
Explanation: Initially, the shortest path from E to C is E→A→C (2 steps). If we remove edge A-E, the new shortest path becomes E→F→B→A→C or E→F→D→C (3 steps), increasing the distance by 1. Other edge removals create smaller increases: removing A-C makes A to D go from A→C→D to A→B→D (both 2 steps, no increase). Removing B-D makes A to F stay A→B→F (2 steps). Removing D-F makes B to E go B→A→E (still 2 steps). Choice A shows no actual increase. Choices B and D have alternative paths that don't increase distance as much.

Question 5

In a social network graph representing friendships among 8 people, the adjacency matrix has exactly 12 ones above the main diagonal. Two people decide to end their friendship, and one new friendship is formed between two people who weren't previously connected. What is the total number of edges in the modified network?

  1. 10 edges representing bidirectional friendships
  2. 11 edges representing bidirectional friendships
  3. 12 edges representing bidirectional friendships (correct answer)
  4. 13 edges representing bidirectional friendships
Explanation: In an undirected friendship graph, the adjacency matrix is symmetric. If there are 12 ones above the diagonal, there are also 12 ones below the diagonal, representing the same 12 friendships (edges). When one friendship ends, we lose 1 edge (12-1=11). When one new friendship forms, we gain 1 edge (11+1=12). Choice A miscounts the initial edges. Choice B forgets to add the new friendship. Choice D incorrectly adds instead of replacing.

Question 6

In a round-robin tennis tournament, every player plays every other player exactly once. The results can be represented by a directed graph where an edge from player ii to player jj means that ii defeated jj.

In a tournament with four players (P1, P2, P3, P4), the results were: P1 defeated P2 and P4; P2 defeated P3; P3 defeated P1 and P4; P4 defeated P2. Which adjacency matrix correctly represents these results, where the entry in row ii, column jj is 1 if player ii defeated player jj?

  1. (correct answer)
Explanation: We need to create a matrix AA where Aij=1A_{ij}=1 if player ii defeated player jj. Let's go row by row: Row 1 (P1): P1 defeated P2 and P4. So, A12=1A_{12}=1 and A14=1A_{14}=1. Row is [0,1,0,1][0, 1, 0, 1]. Row 2 (P2): P2 defeated P3. So, A23=1A_{23}=1. Row is [0,0,1,0][0, 0, 1, 0]. Row 3 (P3): P3 defeated P1 and P4. So, A31=1A_{31}=1 and A34=1A_{34}=1. Row is [1,0,0,1][1, 0, 0, 1]. Row 4 (P4): P4 defeated P2. So, A42=1A_{42}=1. Row is [0,1,0,0][0, 1, 0, 0]. Combining these rows gives the matrix in option A. Distractor B is the transpose of the correct matrix (ATA^T), which confuses 'defeated' with 'was defeated by'. Distractor C incorrectly models some relationships as symmetric (e.g., assumes if P1 beat P2, then P2 beat P1). Distractor D makes an error in Row 2, incorrectly stating P2 defeated P1.

Question 7

A campus shuttle service operates between four locations: the Library (L), Dorms (D), Science Center (S), and Gymnasium (G). There are one-way routes from L to D, D to S, S to G, and G to L. There is also a two-way route between the Library and the Science Center. Using the vertex ordering (L, D, S, G), which is the adjacency matrix for this network?

  1. (correct answer)
Explanation: Let the vertices be ordered (L, D, S, G). An entry Aij=1A_{ij}=1 means there is a route from location ii to location jj. Row 1 (L): One-way to D (A12=1A_{12}=1) and two-way with S (so one-way to S, A13=1A_{13}=1). Row is [0,1,1,0][0, 1, 1, 0]. Row 2 (D): One-way to S (A23=1A_{23}=1). Row is [0,0,1,0][0, 0, 1, 0]. Row 3 (S): One-way to G (A34=1A_{34}=1) and two-way with L (so one-way to L, A31=1A_{31}=1). Row is [1,0,0,1][1, 0, 0, 1]. Row 4 (G): One-way to L (A41=1A_{41}=1). Row is [1,0,0,0][1, 0, 0, 0]. Assembling these rows gives the matrix in option A. Distractor B is the transpose matrix. Distractor C treats all routes as two-way. Distractor D incorrectly omits the two-way nature of the L-S route, only including S to L but not L to S.

Question 8

A research project requires collaboration between 3 statisticians (S1, S2, S3) and 4 programmers (P1, P2, P3, P4). A bipartite graph is used to show which individuals can work together. The possible pairings are: S1 with P2 and P4; S2 with P1 and P2; and S3 with P3 and P4.

If an adjacency matrix is created for this bipartite graph with the vertices ordered (S1, S2, S3, P1, P2, P3, P4), the matrix will have the block structure A=(0BBT0)A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}. What is the 3×43 \times 4 submatrix BB?

  2. (correct answer)
Explanation: When you encounter bipartite graph adjacency matrices, remember that these graphs have two distinct sets of vertices with edges only between the sets, never within them. This creates a special block structure where the adjacency matrix has zeros along the diagonal blocks and the connections are captured in off-diagonal blocks. To find submatrix B, you need to systematically check which statisticians can work with which programmers. The rows of B represent statisticians (S1, S2, S3) and columns represent programmers (P1, P2, P3, P4). Place a 1 where there's a connection, 0 otherwise. From the given pairings:
  • S1 connects to P2 and P4: Row 1 = (0, 1, 0, 1)
  • S2 connects to P1 and P2: Row 2 = (1, 1, 0, 0)
  • S3 connects to P3 and P4: Row 3 = (0, 0, 1, 1)
This gives us $$B = \begin{pmatrix} 0 & 1 & 0 & 1 \ 1 & 1 & 0 & 0 \ 0 & 0 & 1 & 1 \end{pmatrix} AnswerAiswrongbecauseit′sa4×4matrix,butBmustbe3×4(3statisticians×4programmers).AnswerCincorrectlyshowsS3connectedtoP2insteadofP3andP4.AnswerDincorrectlyaddsaconnectionbetweenS2andP4,whichwasn′tgivenintheproblem.∗∗Studytip:∗∗Alwaysdouble−checkmatrixdimensionsfirst,thenmethodicallygothrougheachstatedconnectiontobuildyourmatrixrowbyrow.Thesystematicapproachpreventsmissingoraddingincorrectedges. Answer A is wrong because it's a 4×4 matrix, but B must be 3×4 (3 statisticians × 4 programmers). Answer C incorrectly shows S3 connected to P2 instead of P3 and P4. Answer D incorrectly adds a connection between S2 and P4, which wasn't given in the problem. **Study tip:** Always double-check matrix dimensions first, then methodically go through each stated connection to build your matrix row by row. The systematic approach prevents missing or adding incorrect edges.

Question 9

A small office network consists of five computers: C1, C2, C3, C4, C5. Direct, two-way data connections exist between the following pairs: (C1, C2), (C1, C3), (C2, C3), (C2, C4), (C3, C5), and (C4, C5). If AA is the adjacency matrix representing this network, what is the sum of all entries in AA?

  1. 5
  2. 6
  3. 10
  4. 12 (correct answer)
Explanation: The network can be modeled as an undirected graph where computers are vertices and connections are edges. There are 6 specified connections, so the graph has 6 edges (E=6E=6). For an undirected graph, the sum of all entries in its adjacency matrix AA is equal to twice the number of edges (2E2E). This is because each edge (u,v)(u, v) contributes a 1 to entry AuvA_{uv} and a 1 to entry AvuA_{vu}. Therefore, the sum of all entries is 2×6=122 \times 6 = 12. Distractor B is the number of edges, EE, a common error made by forgetting that each edge is counted twice in the matrix. Distractor A is the number of vertices. Distractor C is the number of non-zero entries on the upper or lower triangle of the matrix, which is 10, but the total sum is 12, not 10. Wait, C1-C3 is a connection, C2-C4 is a connection... Total edges are 6. Let's list non-zero entries: A12,A21,A13,A31,A23,A32,A24,A42,A35,A53,A45,A54A_{12}, A_{21}, A_{13}, A_{31}, A_{23}, A_{32}, A_{24}, A_{42}, A_{35}, A_{53}, A_{45}, A_{54}. There are 12 non-zero entries. So sum is 12. Distractor C is likely a miscalculation, perhaps miscounting the edges as 5 and then doubling.

Question 10

A project involves four tasks: T1, T2, T3, and T4. The dependencies are: T1 must be completed before T2 and T3 can start. Both T2 and T3 must be completed before T4 can start. This network of tasks is represented by a directed graph where an edge from task i to task j means i is a direct prerequisite for j. Let A be the adjacency matrix of this graph. Which of the following statements about A and its powers is true?

  1. The entry A_{14} is 1, representing the dependency of T4 on T1.
  2. The matrix A is symmetric because if T1 is a prerequisite for T2, T2 depends on T1.
  3. The sum of the entries in the column for T4 is 2. (correct answer)
  4. The entry at row 1, column 4 of A^2, which is (A^2)_{14}, is 0.
Explanation: First, we represent the task dependencies as a directed graph. The vertices are T1, T2, T3, T4. The edges are T1→T2, T1→T3, T2→T4, and T3→T4. The adjacency matrix A (with rows/columns ordered 1, 2, 3, 4) is: $$ A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix} $$ A. A_{14} is 0 because T1 is not a direct prerequisite for T4. The path from T1 to T4 has length 2. B. The matrix is not symmetric (e.g., ‘A12`A_{12}=1 but $A_{21}$=0), which is expected for a directed graph representing prerequisites. C. The sum of the entries in a column gives the in-degree of the corresponding vertex. The column for T4 is [0, 1, 1, 0]^T. The sum is 0+1+1+0=2, which correctly indicates that T4 has two direct prerequisites (T2 and T3). D. The entry (A^2){14}represents the number of paths of length 2 from T1 to T4. There are two such paths: T1→T2→T4 and T1→T3→T4. Therefore,(A^2){14} = 2`, not 0.

Question 11

The adjacency matrix A for a simple, undirected social network of five people (P1, P2, P3, P4, P5) is given below. An entry of 1 indicates a friendship. Let N(Pi) denote the set of friends of person Pi. What is the number of people who are friends with both P1 and P2, represented by |N(P1) \cap N(P2)|? $$ A = \begin{pmatrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} $$

  1. 1 (correct answer)
  2. 2
  3. 3
  4. 5
Explanation: To find the number of common friends of P1 and P2, we first need to identify the set of friends for each person.
  1. Find the friends of P1, N(P1): Look at the 1st row (or column) of the matrix. The non-zero entries are in columns 2, 3, and 5. So, N(P1) = {P2, P3, P5}.
  2. Find the friends of P2, N(P2): Look at the 2nd row (or column). The non-zero entries are in columns 1, 3, and 4. So, N(P2) = {P1, P3, P4}.
  3. Find the intersection of these two sets, N(P1) \cap N(P2): This is the set of people who are in both N(P1) and N(P2). Comparing the sets, the only common person is P3. So, N(P1) \cap N(P2) = {P3}.
  4. Find the size of the intersection, |N(P1) \cap N(P2)|: The set contains one person, so the size is 1. Alternatively, this value is given by (A^2)_{12}, which is the dot product of row 1 and column 2: (0)(1) + (1)(0) + (1)(1) + (0)(1) + (1)(0) = 1.

Question 12

The matrix W represents the number of daily flights between four airports: A, B, C, and D. The entry W_{ij} is the number of flights from airport i to airport j. $$ W = \begin{pmatrix} 0 & 10 & 5 & 0 \\ 8 & 0 & 0 & 12 \\ 5 & 0 & 0 & 7 \\ 0 & 15 & 6 & 0 \end{pmatrix} $$ What is the difference between the total number of daily flights departing from airport B and the total number of daily flights arriving at airport D?

  1. 1 (correct answer)
  2. 7
  3. 8
  4. 19
Explanation: This problem requires interpreting the sums of rows and columns in a weighted adjacency matrix.
  1. Total flights departing from airport B: This is the out-degree of vertex B, which is the sum of the entries in the row corresponding to B (the 2nd row). Sum of 2nd row = 8 + 0 + 0 + 12 = 20.
  2. Total flights arriving at airport D: This is the in-degree of vertex D, which is the sum of the entries in the column corresponding to D (the 4th column). Sum of 4th column = 0 + 12 + 7 + 0 = 19.
  3. Difference: The question asks for the difference between these two values. Difference = (Departing from B) - (Arriving at D) = 20 - 19 = 1.

Question 13

A simple, undirected graph is a graph with no loops (edges from a vertex to itself) and no more than one edge between any two distinct vertices. Which of the following matrices cannot be the adjacency matrix for a simple, undirected graph with four vertices?

  1. $$ \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} $$
  2. $$ \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} $$
  3. $$ \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} $$
  4. $$ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} $$ (correct answer)
Explanation: An adjacency matrix A for a simple, undirected graph must have three properties:
  1. All entries must be 0 or 1.
  2. The main diagonal entries must all be 0 (no loops).
  3. The matrix must be symmetric (A = $A^T$, meaning ‘Aij`A_{ij} = AjiA_{ji}). Let's check each choice: A. The diagonal is all 0s. The matrix is symmetric (e.g., $A_{12}==A_{21}=1‘).Allentriesare0or1.Thisisavalidmatrixforasimple,undirectedgraph(a4−cycle).B.Thediagonalisall0s.Thematrixissymmetric.Allentriesare0or1.Thisisavalidmatrixforasimple,undirectedgraph(twodisjointedges).C.Thediagonalisall0s.Thematrixissymmetric.Allentriesare0or1.Thisisavalidmatrixforasimple,undirectedgraph(thecompletegraph‘ = 1`). All entries are 0 or 1. This is a valid matrix for a simple, undirected graph (a 4-cycle). B. The diagonal is all 0s. The matrix is symmetric. All entries are 0 or 1. This is a valid matrix for a simple, undirected graph (two disjoint edges). C. The diagonal is all 0s. The matrix is symmetric. All entries are 0 or 1. This is a valid matrix for a simple, undirected graph (the complete graph `K_4$). D. This matrix has a 1on its main diagonal at positionA_{22}`. This represents a loop from vertex 2 to itself, which is not allowed in a simple graph. Therefore, this matrix cannot be the adjacency matrix for a simple, undirected graph.

Question 14

The matrix M below is the adjacency matrix for a directed graph G, where M_{ij}=1 indicates an edge from vertex i to vertex j. $$ M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix} $$ Which of the following statements accurately describes the graph G?

  1. G is an undirected graph because the total number of 1s is even.
  2. Every vertex in G has an out-degree of at least 1. (correct answer)
  3. The underlying undirected graph of G is not connected.
  4. The graph G contains no cycles.
Explanation: When you encounter an adjacency matrix for a directed graph, you need to understand how to extract key properties directly from the matrix structure. The rows represent starting vertices, and columns represent ending vertices, so Mij=1M_{ij} = 1 means there's a directed edge from vertex ii to vertex jj. To find the out-degree of each vertex, sum the entries in each row. For vertex 1: 0+1+1+0=20+1+1+0 = 2. For vertex 2: 0+0+1+1=20+0+1+1 = 2. For vertex 3: 0+0+0+1=10+0+0+1 = 1. For vertex 4: 1+0+0+0=11+0+0+0 = 1. Since every vertex has at least one outgoing edge, option B is correct. Option A is wrong because the number of 1s in an adjacency matrix has nothing to do with whether a graph is directed or undirected. The defining characteristic of an undirected graph is that its adjacency matrix is symmetric (if Mij=1M_{ij} = 1, then Mji=1M_{ji} = 1), which this matrix clearly isn't. Option C is incorrect because you can trace paths between all vertices. For example, from vertex 3 you can reach vertex 1 via the path 3→4→13 \to 4 \to 1, and from vertex 1 you can reach vertex 3 via 1→2→31 \to 2 \to 3. Option D is false because the graph contains the cycle 1→2→3→4→11 \to 2 \to 3 \to 4 \to 1, which you can verify by following the 1s in the matrix. Remember: for adjacency matrices, row sums give out-degrees, column sums give in-degrees, and symmetry indicates whether the graph is undirected.

Question 15

In a round-robin tournament, four teams (1, 2, 3, 4) play each other exactly once. The results are represented by an adjacency matrix M where M_{ij} = 1 if team i beat team j, and M_{ij} = 0 otherwise. Given that team 1 beat team 2 and team 3 beat team 1, which of the following matrices could represent the complete results of the tournament?

  1. $$ \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} $$
  2. $$ \begin{pmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} $$ (correct answer)
  3. $$ \begin{pmatrix} 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix} $$
  4. $$ \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} $$
Explanation: When you encounter adjacency matrix problems for tournaments, remember that these matrices have strict structural requirements. In a round-robin tournament, each team plays every other team exactly once, so the matrix must be antisymmetric (if team i beats team j, then team j cannot beat team i) and have zeros on the diagonal (teams don't play themselves). Start by identifying the given constraints: team 1 beat team 2 (position (1,2) = 1, position (2,1) = 0) and team 3 beat team 1 (position (3,1) = 1, position (1,3) = 0). Any valid matrix must satisfy these conditions. Option B correctly satisfies both constraints and maintains antisymmetry throughout. Position (1,2) = 1 and (2,1) = 0 ✓, position (3,1) = 1 and (1,3) = 0 ✓. Every other pair also follows the antisymmetric rule where exactly one team beats the other. Option A fails because it has (1,3) = 1 when we need (1,3) = 0, directly contradicting the given information that team 3 beat team 1. Option C violates the diagonal rule with (2,2) = 1 and (3,3) = 1, which is impossible since teams cannot play themselves. It also breaks antisymmetry in multiple places. Option D incorrectly has (1,2) = 0 when the problem states team 1 beat team 2, so (1,2) must equal 1. Study tip: For tournament matrices, always check three things in order: given constraints first, then diagonal zeros, then antisymmetry. This systematic approach will catch errors quickly and help you identify valid tournament structures.

Question 16

Let AA be the adjacency matrix of a simple, undirected graph GG with vertices v1,v2,…,vnv_1, v_2, \dots, v_n. What is the correct interpretation of the entry (A2)ii(A^2)_{ii} on the main diagonal of A2A^2?

  1. It is always zero for a simple graph.
  2. It represents the number of triangles in the graph that include vertex viv_i.
  3. It is equal to the degree of vertex viv_i. (correct answer)
  4. It is equal to 1 if viv_i is part of a cycle, and 0 otherwise.
Explanation: The entry (A2)ii(A^2)_{ii} represents the number of walks of length 2 from vertex viv_i to itself. A walk of length 2 from viv_i to viv_i is of the form vi→vk→viv_i \rightarrow v_k \rightarrow v_i for some vertex vkv_k. Since the graph is simple, there are no loops, so k≠ik \neq i. An edge from viv_i to vkv_k and an edge from vkv_k to viv_i exist for every neighbor vkv_k of viv_i. The number of such walks is therefore the number of neighbors of viv_i, which is, by definition, the degree of viv_i. Mathematically, (A2)ii=∑k=1nAikAki(A^2)_{ii} = \sum_{k=1}^n A_{ik}A_{ki}. For an undirected graph, Aki=AikA_{ki}=A_{ik}, so (A2)ii=∑k=1n(Aik)2(A^2)_{ii} = \sum_{k=1}^n (A_{ik})^2. Since AikA_{ik} is 0 or 1, (Aik)2=Aik(A_{ik})^2 = A_{ik}. Thus, (A2)ii=∑k=1nAik=deg(vi)(A^2)_{ii} = \sum_{k=1}^n A_{ik} = \text{deg}(v_i). Distractor A is incorrect; AiiA_{ii} is always zero for a simple graph, but (A2)ii(A^2)_{ii} is not. Distractor B describes a property related to the diagonal of A3A^3. Distractor D is an incorrect interpretation; the degree is not a binary property.