Question: c) Considering the graph below: A B C D E F G (i) Write the degree of each vertex of the graph. (2 marks) (ii) Identify whether the graph contains an Euler circuit. If it does, write down the Euler circuit by listing the vertices in the order they are visited, starting and ending at vertex F. If it does not, explain why. (2 marks) (iii) Identify whether the graph contains an Euler path. If it does, write down the Euler path by listing the vertices in the order they are visited, starting at vertex G. If it does not, explain why. (2 marks) (iv) Identify whether the graph has a Hamiltonian circuit. If it does, write down the Hamiltonian circuit by listing the vertices in the order they are visited, starting and ending at vertex A. If it does not, explain why. (2 marks) [Total: 25 marks] Graph description: top-center graph with vertices A, B, C, D, E, F, G; edges A-B, A-D, B-G, D-F, C-D, C-E, E-F, F-G, and D-G.

1. **Problem Statement:** We have a graph with vertices $A, B, C, D, E, F, G$ and edges $A-B, A-D, B-G, D-F, C-D, C-E, E-F, F-G,$ and $D-G$. We need to find: (i) The degree of each vertex. (ii) Whether the graph contains an Euler circuit starting and ending at $F$. (iii) Whether the graph contains an Euler path starting at $G$. (iv) Whether the graph has a Hamiltonian circuit starting and ending at $A$. 2. **Step (i): Degree of each vertex** - The degree of a vertex is the number of edges incident to it. - Calculate degrees: - $\deg(A) = 2$ (edges $A-B$, $A-D$) - $\deg(B) = 2$ (edges $A-B$, $B-G$) - $\deg(C) = 2$ (edges $C-D$, $C-E$) - $\deg(D) = 4$ (edges $A-D$, $C-D$, $D-F$, $D-G$) - $\deg(E) = 2$ (edges $C-E$, $E-F$) - $\deg(F) = 3$ (edges $D-F$, $E-F$, $F-G$) - $\deg(G) = 3$ (edges $B-G$, $D-G$, $F-G$) 3. **Step (ii): Euler Circuit** - An Euler circuit exists if the graph is connected and every vertex has even degree. - Check degrees: $A(2)$ even, $B(2)$ even, $C(2)$ even, $D(4)$ even, but $F(3)$ odd, $G(3)$ odd. - Since vertices $F$ and $G$ have odd degree, **no Euler circuit exists**. 4. **Step (iii): Euler Path** - An Euler path exists if the graph is connected and exactly two vertices have odd degree. - Odd degree vertices are $F$ and $G$ (both degree 3). - Since there are exactly two odd degree vertices, an Euler path exists starting at one odd vertex and ending at the other. - Starting at $G$, one Euler path is: $$G - B - A - D - C - E - F - D - G - F$$ 5. **Step (iv): Hamiltonian Circuit** - A Hamiltonian circuit visits every vertex exactly once and returns to the start. - Check if such a circuit exists starting and ending at $A$. - One possible Hamiltonian circuit is: $$A - B - G - F - E - C - D - A$$ **Final answers:** (i) Degrees: $A=2$, $B=2$, $C=2$, $D=4$, $E=2$, $F=3$, $G=3$ (ii) No Euler circuit because vertices $F$ and $G$ have odd degree. (iii) Euler path exists starting at $G$: $G - B - A - D - C - E - F - D - G - F$ (iv) Hamiltonian circuit exists starting and ending at $A$: $A - B - G - F - E - C - D - A$