Problem
COM-B1-M11-P005 Degrees
#5
★☆☆☆☆ Level 1 of 5
A graph has vertex degrees \(1,2,2,3,4\). Can such a graph exist?
Check the degree sum.
The degree sum is \(12\), so parity does not forbid it. Construct one explicitly. Name the vertices \(A,B,C,D,E\). Connect \(A\) to all other vertices: then \(A\) has degree \(4\), and all others currently have degree \(1\). Now add edges \(BC\) and \(BD\). The degrees are \(\deg A=4\), \(\deg B=3\), \(\deg C=2\), \(\deg D=2\), \(\deg E=1\). Therefore such a graph exists.
Important: even degree sum is necessary but not always sufficient; here a construction is needed.