Problem Detail: For school we have to make an assignment, and part of the assignment is this question:
Describe an unidrected graph that has 12 edges and at least 6 vertices. 6 of the vertices have to have degree exactly 3, all other vertices have to have degree less than 2. Use as few vertices as possible.
The best solution I came up with is the following one. Here the number in the circles is the degree of that vertex, now I was wondering if there is a better solution, if so, can somebody explain this to me? 
I do not need a better answer, just a push in the right direction – if needed.
Asked By : user16029
Answered By : A.Schulz
You have 12 edges, so the sum of the vertex degree is 24. Then there are 6 degree-3 vertices taking away 18. Thus the best you can hope for are 3 vertices of degree 2. Thus you found the solution.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22972
