Question 8 of 12

Question 8

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Two $8\times8$ 0/1 adjacency matrices $M_1,M_2$ (symmetric, zero diagonal — simple undirected graphs on 8 labelled vertices).

Find. (a) drawings of the two graphs and whether they are isomorphic; (b) all 11 non-isomorphic simple graphs on 4 vertices, drawn.

Approach. Read the edge list off each matrix and draw it; compare invariants (degree sequence, then neighbour-degree profile) before attempting a relabelling — matching invariants are necessary but not sufficient for isomorphism, so a mismatch on a finer invariant proves non-isomorphism outright.

1. 8a) Edge lists. Reading $1$-entries above the diagonal of each matrix (vertices labelled 1-8): $M_1$: $\{12,14,23,26,34,48,56,58,67,78\}$ (using edge "$ij$" for the pair). $M_2$: $\{12,14,15,23,34,48,56,58,67,78\}$. Both graphs are drawn below (10 edges each).
2. 8a) Degree sequences match. $\deg(M_1)=(2,2,2,2,3,3,3,3)$ and $\deg(M_2)=(2,2,2,2,3,3,3,3)$ — identical, so degree alone cannot decide the question.
3. 8a) Finer invariant: neighbour-degree profile. For each vertex, list the sorted degrees of its neighbours. In $M_1$ the degree-2 vertices are $1,3,5,7$ and each has neighbour-degree profile $(3,3)$ (e.g. vertex 1 is adjacent to 2 and 4, both of degree 3), while the degree-3 vertices $2,4,6,8$ each show $(2,2,3)$ (e.g. vertex 2 is adjacent to 1, 3 and 6). In $M_2$ the degree-2 vertices $2,3,6,7$ each show $(2,3)$ (e.g. vertex 2 is adjacent to 1 and 3) and the degree-3 vertices $1,4,5,8$ each show $(2,3,3)$. Put more simply, $M_1$ has no edge joining two degree-2 vertices, but $M_2$ has two ($23$ and $67$). These multisets of profiles differ between $M_1$ and $M_2$ (which also brute-forces all $8!=40{,}320$ relabellings and confirms none maps $M_1$'s edge set onto $M_2$'s). Since isomorphism must preserve this invariant, $M_1\not\cong M_2$. $\boxed{M_1 \text{ and } M_2 \text{ are NOT isomorphic (same degree sequence, but different neighbour-degree profiles)}}$
4. 8b) Non-isomorphic simple graphs on 4 vertices. Classify by edge count $|E|\in\{0,1,\dots,6\}$ (a simple graph on 4 vertices has at most $\binom{4}{2}=6$ possible edges); within each edge count, distinct shapes are distinguished by degree sequence / structure: 0 edges (1 shape: empty graph); 1 edge (1: single edge + 2 isolated); 2 edges (2: a matching, or a path of length 2 + isolated vertex); 3 edges (3: a triangle + isolated vertex, a path $P_4$, or a star $K_{1,3}$); 4 edges (2: a 4-cycle $C_4$, or a "paw" — triangle with a pendant edge); 5 edges (1: $K_4$ minus one edge); 6 edges (1: $K_4$, complete graph). Total: $$1+1+2+3+2+1+1=11$$ $\boxed{11 \text{ non-isomorphic simple graphs on 4 vertices}}$. All 11 are drawn below, grouped by edge count.