Draw a graph with the specified properties or show that no s

Draw a graph with the specified properties or show that no such graph exists. Graph with four vertices of degrees 1, 2, 3, and 3.

What I have so far. I\'m sure that it should not be this long.

No graph exists.

Suppose there are four vertices A, B, C and D with degrees 1, 2, 3, and 3, respectively. If vertex A has a degree of 1, it is connected to one other vertex.

Case 1

It is connected to vertex B, which has a degree of 2. Then B must be connected to a vertex of degree 3, vertex C. In order for Vertex C to have degree 3 it must either be looped to itself or have two parallel edges to vertex D. If it loops to itself there is no way for vertex D to have degree 3 as it would only contain loops which would result in an even degree. If it has 2 parallel edges to vertex D, vertex D can not have degree 3, it would have degree 2 unless loops were added to D would result in 2+ even number which is a even degree. Therefor A cannot connect to B

Case 2

A is connected to vertex C with degree 3. Then C must either loop to itself, have parallel edges to B or D, or have edges to both B and D. The same argument applies if A connects to D as they both have degree 3 and are there for argumentatively equivalent.

Subcase 1

C loops to itself, do C has degree 3 and A degree 1. B must have degree 2 so it must either loop to itself or have parallel edges to D. If it loops to itself it D cannot have degree 3 as it could only have loops, which produce even degrees. If it has two parallel edges to D, D would have an even degree as it would either be 2 or 2+2(number of loops), which is not the three required. So C cannot loop to itself.

Subcase 2

C has parallel edges to B. If C has two parallel edges to B then B will have degree 2 as required but D must then loop to itself to produce a degree of three which is not possible as loops only produce even degrees. There for C and B cannot have parallel edges.

Subcase 3

C has parallel edges to D. If C has two parallel edges to D, then D must have an edge to B in order to have degree 3. (loops will only produce 2+2(number of loops) so loops will not get to the required degree of 3). This leaves B with degree 1 and only loops to itself can be added with will result in 1+2(number of loops) so loops will not get to the required degree of 2. There for C can not have parallel edges to D.

Subcase 4

C has edges to both B and D. In which case B, which has degree 2 must have an edge to D (as loops will only produce 1+2(number of loops) so loops will not get to the required degree of 2) this gives D a degree of 2 and only loops are allowed which produces only 2+2(number of loops), which is not the three required.

Therefore it is not possible for a graph with four vertices of degrees 1, 2, 3, and 3 to exist.

Solution