04-BS-16, December 2014, Q10 | Nivaar Exam Prep

Question 10

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 $4\times4$ symmetric 0/1 adjacency matrices $M_1,M_2$ with zero diagonal (loop-free, undirected). A party of 15 people, each proposed to shake hands with exactly 3 others.

Find. (a1) The graphs $G_1,G_2$ drawn from $M_1,M_2$ (label rows/columns 1–4 as $a,b,c,d$ and $w,x,y,z$). (a2) Whether $G_1\cong G_2$, justified. (b) Whether the handshake configuration is possible.

Approach. Read edges directly off each matrix's 1-entries, check the isomorphism-invariant degree sequence first, then search for an explicit vertex bijection preserving adjacency; for (b) apply the handshaking lemma (sum of degrees is always even).

$G_1$ (vertices $a,b,c,d$) and $G_2$ (vertices $w,x,y,z$), edges read from the two adjacency matrices.

a1) Read the edges off each matrix. $M_1$'s 1-entries give $G_1$ edges $\{a,b\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}$ (5 edges). $M_2$'s 1-entries give $G_2$ edges $\{w,x\},\{w,y\},\{w,z\},\{x,y\},\{y,z\}$ (5 edges) — see the figure above.
a2) Compare degree sequences. $G_1$ degrees: $\deg a=2,\deg b=3,\deg c=2,\deg d=3$, sequence $(3,3,2,2)$. $G_2$ degrees: $\deg w=3,\deg x=2,\deg y=3,\deg z=2$, sequence $(3,3,2,2)$. Degree sequences match (necessary condition), edge counts match (5 each) — isomorphism is possible; now find the bijection.
a2) Exhibit the isomorphism. Match the degree-3 vertices to degree-3 vertices and degree-2 to degree-2: try $a\mapsto x,\ b\mapsto w,\ c\mapsto z,\ d\mapsto y$. Check every $G_1$ edge maps to a $G_2$ edge: $\{a,b\}\mapsto\{x,w\}$✓, $\{a,d\}\mapsto\{x,y\}$✓, $\{b,c\}\mapsto\{w,z\}$✓, $\{b,d\}\mapsto\{w,y\}$✓, $\{c,d\}\mapsto\{z,y\}$✓ — all five map onto the five $G_2$ edges bijectively. $\boxed{G_1\cong G_2 \text{ via } a\mapsto x,\ b\mapsto w,\ c\mapsto z,\ d\mapsto y}$
b) Apply the handshaking lemma. Model the 15 people as vertices, handshakes as edges; "each shakes exactly 3 others" means every vertex has degree exactly 3, so the sum of all degrees would be $15\times3=45$. The Handshaking Lemma states the sum of vertex degrees in any graph equals twice the number of edges, hence must always be EVEN. Since $45$ is odd, no such graph can exist. $\boxed{\text{NOT possible} \text{ — 15 people each shaking exactly 3 hands would force an odd degree-sum (45), violating the handshaking lemma}}$.

Question 10 results
Part	Result
a1	$G_1$: 5 edges on $a,b,c,d$; $G_2$: 5 edges on $w,x,y,z$ (see figure)
a2	Isomorphic: $a\mapsto x,\ b\mapsto w,\ c\mapsto z,\ d\mapsto y$
b	Not possible — degree sum $45$ is odd, violates handshaking lemma

Topic: Graph isomorphism; the handshaking lemma.

Key relations: $\sum_v \deg(v)=2|E|$ (handshaking lemma, always even); isomorphism requires matching degree sequences (necessary but not sufficient) plus an explicit adjacency-preserving bijection.

Why this works: Every edge contributes exactly 2 to the total degree count (one at each endpoint), so the sum is always even regardless of the graph's structure — an odd target sum is an instant impossibility proof requiring no case analysis.

Common pitfall: Stopping at "degree sequences match" and declaring graphs isomorphic without exhibiting the actual bijection — matching degree sequences is necessary but two non-isomorphic graphs can share a degree sequence, so the explicit vertex map (and edge-by-edge check) is required for a rigorous justification.

Source: Rosen, Discrete Mathematics and Its Applications, 7th ed., Ch. 10.1–10.2 (Graphs, Graph Isomorphism).

Question 10 of 12

Question 10