Build 6vertex graphs with the following degrees of vertices

Build 6-vertex graphs with the following degrees of vertices, if possible. If not possible, explain why not. (a) Three vertices of degree 3 and three vertices of degree 1 (b) Vertices of degrees 1,2,2,3,4,5 (c) Vertices of degrees 2,2,4,4,4,4

Solution

(b)A 6-Vertex graph with the following degrees of  vertices, whose degrees are 1,2,2,3,4,5

By the Handshaking Theorem, we have that the sum of the degrees across all vertices in a graph will always be even. The sum of the vertices given for this graph is odd, and so this graph cannot exist.

(C) A graph with 6 vertices, whose degrees are 2,2,4,4,4,4..

This graph satisfies the Handshaking Theorem in that the sum of the vertices is even. The problem lies in the fact that one of the vertices has  five edges, and therefore, there must be five incident vertices, but in this graph, although there are five other vertices, one of them is reported as having no incident edges. Since a simple graph cannot have loops or multiple edges, it is impossible to have a vertex in this graph which connects to five vertices when one of the only other five vertices is not accepting an edge. This means that this graph cannot exist.