1. **Problem Statement:** Prove that there is no simple graph with five vertices having degrees 4, 4, 4, 2, 2. 2. **Key Concept:** The sum of the degrees of all vertices in a graph must be even (Handshaking Lemma), and the degree sequence must be graphical (i.e., realizable by a simple graph). 3. **Sum of degrees:** Calculate the sum: $$4 + 4 + 4 + 2 + 2 = 16$$ This sum is even, so it passes the first check. 4. **Check graphicality using the Havel-Hakimi algorithm:** - Start with the sequence sorted in non-increasing order: $$[4,4,4,2,2]$$ - Remove the first degree (4), then subtract 1 from the next 4 degrees: - Remaining degrees: $$[4,4,2,2]$$ - Subtract 1 from the next 4 degrees: $$[3,3,1,1]$$ - New sequence: $$[3,3,1,1]$$ 5. **Repeat the process:** - Sort: $$[3,3,1,1]$$ - Remove the first degree (3), subtract 1 from the next 3 degrees: - Remaining degrees: $$[3,1,1]$$ - Subtract 1: $$[2,0,0]$$ - New sequence: $$[2,0,0]$$ 6. **Repeat again:** - Sort: $$[2,0,0]$$ - Remove the first degree (2), subtract 1 from the next 2 degrees: - Remaining degrees: $$[0,0]$$ - Subtract 1: $$[-1,-1]$$ - Negative degrees appear, which is impossible. 7. **Conclusion:** Since the Havel-Hakimi process leads to negative degrees, the sequence $$[4,4,4,2,2]$$ is not graphical. Therefore, no simple graph with five vertices having degrees 4,4,4,2,2 exists. --- 8. **Second part: Draw a simple graph with degrees 2,3,3,3,3.** - The sum of degrees is $$2 + 3 + 3 + 3 + 3 = 14$$, which is even. - The given pentagon graph with vertices a,b,c,d,e and edges: - a connected to b,e (degree 2) - b connected to a,c,d (degree 3) - c connected to b,d,e (degree 3) - d connected to b,c,e (degree 3) - e connected to a,c,d (degree 3) - This matches the degree sequence $$[2,3,3,3,3]$$. **Final answer:** No simple graph exists with degrees 4,4,4,2,2. A simple graph with degrees 2,3,3,3,3 is the pentagon with edges as described.