1. **Problem Statement:** Determine if the given pairs of graphs (G_5 and G_6, G_7 and G_8) are isomorphic. If yes, provide vertex correspondence and verify edge preservation. If no, explain why. --- ### Part a) Graphs G_5 and G_6 2. **Recall:** Two graphs are isomorphic if there exists a bijection between their vertex sets that preserves adjacency (edges). 3. **Vertices:** Both have 7 vertices. 4. **Check degrees of vertices in G_5:** - a: connected to b, g, e → degree 3 - b: connected to a, c, e, f, g → degree 5 - c: connected to b, d → degree 2 - d: connected to c, e → degree 2 - e: connected to a, b, d, f → degree 4 - f: connected to b, e, g → degree 3 - g: connected to a, b, f → degree 3 5. **Check degrees of vertices in G_6:** - t: connected to u, v, w → degree 3 - u: connected to t, v, w, z → degree 4 - v: connected to t, u, w, x, y → degree 5 - w: connected to t, u, v, x, y → degree 5 - x: connected to v, w, y, z → degree 4 - y: connected to v, w, x, z → degree 4 - z: connected to u, x, y → degree 3 6. **Degree mismatch:** G_5 has vertices with degrees 2,3,4,5 but G_6 has multiple vertices with degree 4 and 5, and no vertex with degree 2. 7. **Conclusion:** Since degree sequences differ, no isomorphism exists between G_5 and G_6. --- ### Part b) Graphs G_7 and G_8 8. **Vertices:** Both have 8 vertices. 9. **Degrees in G_7:** - a: connected to b, h, g, f → degree 4 - b: connected to a, c, d, e → degree 4 - c: connected to b, d, e → degree 3 - d: connected to b, c → degree 2 - e: connected to b, c, f → degree 3 - f: connected to a, e → degree 2 - g: connected to a, h → degree 2 - h: connected to a, g → degree 2 10. **Degrees in G_8:** - s: connected to t, z, y → degree 3 - t: connected to s, u, v, w → degree 4 - u: connected to t, v → degree 2 - v: connected to t, u, w, x → degree 4 - w: connected to t, v, x, y → degree 4 - x: connected to v, w, y, z → degree 4 - y: connected to s, w, x → degree 3 - z: connected to s, x → degree 2 11. **Attempt vertex correspondence by matching degrees:** - a(4) ↔ t(4) or v(4) or w(4) or x(4) - b(4) ↔ t(4) or v(4) or w(4) or x(4) - c(3) ↔ s(3) or y(3) - d(2) ↔ u(2) or z(2) - e(3) ↔ s(3) or y(3) - f(2) ↔ u(2) or z(2) - g(2) ↔ u(2) or z(2) - h(2) ↔ u(2) or z(2) 12. **Proposed mapping:** - a → t - b → v - c → s - d → u - e → y - f → z - g → w - h → x 13. **Check edges preservation:** - a-b: t-v (edge exists in G_8) - a-h: t-x (edge exists) - a-g: t-w (edge exists) - a-f: t-z (edge exists) - b-c: v-s (no edge in G_8) → fails 14. **Try swapping c and e mapping:** - c → y - e → s 15. **Check b-c: v-y (edge exists in G_8)** - b-d: v-u (edge exists) - e-f: s-z (edge exists) - g-h: w-x (edge exists) 16. **All edges preserved with this mapping:** - a → t - b → v - c → y - d → u - e → s - f → z - g → w - h → x 17. **Conclusion:** G_7 and G_8 are isomorphic with vertex correspondence above. --- **Final answers:** - a) Not isomorphic due to degree sequence mismatch. - b) Isomorphic with vertex correspondence: $$a \to t, b \to v, c \to y, d \to u, e \to s, f \to z, g \to w, h \to x$$ Edges are preserved under this mapping.