Plot simple graph given 4 vertices

$\begingroup$

Draw a graph with the specified properties or show (prove) that no such graph exists:

A simple graph with four vertices of degrees 1, 1, 3, and 3

Maximum number of edges = nC2 (where n is the number of vertices) = 4(4-1)/2 = 6
Total degree = 1 + 1 + 3 +3 = 8
Number of edges this graph have = 8/2 = 4

Theoritically, this graph should be possible but I'm having trouble drawing this graph. I always end up with 3 vertices having a degree of 2 each and the other vertex having a degree of 1, so I'm not really not sure what I'm supposed to do here.

$\endgroup$ 2

1 Answer

$\begingroup$

Since there are two vertices of degree $3$ there are two vertices adjacent to all the other vertices. Then the other two vertices are adjacent to both of these, so there is no vertex of degree $1$.

No such graph exists.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy