Is it possible to make a graph with four vertices of degree 2, 3, 4, and 2?

1 Answer | Add Yours

grebjack's profile pic

grebjack | High School Teacher | (Level 1) Adjunct Educator

Posted on

Nope. 

Every edge connecting vertices has two endpoints.  So if you start with a bunch of unconnected vertices, they are all degree 0 and the sum of the degrees is 0, an even number.  If you add an edge between two of those vertices, now you have two vertices of degree 1 and everything else has a degree of 0, so now the sum of the degrees is 2, again an even number.  If you added the edge so that it had both endpoints at the same vertex, you'd have one vertex with degree 2 and everything else degree 0, so the sum of the degrees is still 2.  Every time you add another edge, the sum of the degrees goes up by 2 more.  So the sum of the degrees is always an even number. 

In the problem you pose, the sum of the degrees is 11, so you'd need 5 1/2 edges, and there is no way to put half an edge into your graph.

We’ve answered 318,955 questions. We can answer yours, too.

Ask a question