1. **Problem Statement:** Prove that there is no simple graph with five vertices having degrees 4,4,4,2,2. Draw a simple graph with five vertices having degrees 2,3,3,3,3 if possible. 2. **Key Formula and Rules:** - The sum of degrees of all vertices in a graph equals twice the number of edges: $$\sum d_i = 2|E|$$. - In a simple graph, the degree of any vertex cannot exceed the number of other vertices (max degree is $n-1$). - The Handshaking Lemma: sum of degrees must be even. 3. **Part 1: Prove no graph with degrees 4,4,4,2,2 exists.** - Sum of degrees: $4+4+4+2+2=16$. - Number of edges: $\frac{16}{2}=8$. - Maximum edges in a simple graph with 5 vertices: $\binom{5}{2}=10$. - Check if degree sequence is graphical using the Havel-Hakimi algorithm: - Sequence: 4,4,4,2,2 - Remove largest degree 4, reduce next 4 degrees by 1: New sequence: 3,3,1,2 (sorted: 3,3,2,1) - Remove largest degree 3, reduce next 3 degrees by 1: New sequence: 2,1,0 (sorted: 2,1,0) - Remove largest degree 2, reduce next 2 degrees by 1: New sequence: 0, -1 (negative degree impossible) Since negative degree appears, the sequence is not graphical. Hence, no such simple graph exists. 4. **Part 2: Draw a graph with degrees 2,3,3,3,3.** - Sum of degrees: $2+3+3+3+3=14$. - Number of edges: $\frac{14}{2}=7$. - Construct graph: - Label vertices $v_1$ to $v_5$. - Assign $v_1$ degree 2, others degree 3. - Connect $v_1$ to $v_2$ and $v_3$ (degree of $v_1$ is 2). - Connect $v_2$ to $v_3$, $v_4$, $v_5$ (degree 3). - Connect $v_3$ to $v_4$, $v_5$ (degree 3). - Connect $v_4$ to $v_5$ (degree 3). This satisfies all degree requirements. **Final answers:** - No simple graph with degrees 4,4,4,2,2 exists. - A simple graph with degrees 2,3,3,3,3 can be constructed as described.