$\begingroup$
$\endgroup$
2
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.
1 Answer
$\begingroup$
$\endgroup$
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.
