[Solved]: Undirected graph with 12 edges and 6 vertices

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