ITPEC FE Subject A October 2024 Question 4

Edges a–b, b–c, b–d, c–d, c–e, e–f — read each 1 above the diagonal of the symmetric matrix as one edge, then find the drawing with exactly these six.

• •Row a: 1 under b → a–b
• •Row b: 1 under c and d → b–c, b–d
• •Row c: 1 under d and e → c–d, c–e
• •Row d: no 1 right of the diagonal (its 1s under b and c are already counted)
• •Row e: 1 under f → e–f

All four drawings share a–b, e–f, the arc c–e over the top and the arc b–d underneath, so the straight edges between neighbours decide it: the graph needs b–c and c–d but not d–e. Only (c) draws exactly that.

Answer (c)

Why not others:

• •(a) — has no b–c edge (row b, column c is 1) and adds d–e (row d, column e is 0)
• •(b) — has no c–d edge (row c, column d is 1) and adds d–e
• •(d) — draws all five neighbour edges, seven edges in total; the extra d–e contradicts the 0 at row d, column e

Key rule: An undirected graph's adjacency matrix is symmetric, so count only the upper triangle: each 1 is one edge, and the 1s in a row give that node's degree.

Basic Theory · AI-written, may contain errors