1
$\begingroup$

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?

Solution exercise 1

I do not need a better answer, just a push in the right direction - if needed.

$\endgroup$

closed as off-topic by Juho, vonbrand, G. Bach, David Richerby, Artem Kaznatcheev Mar 27 '14 at 7:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Your graph has only $11$ edges. It's pretty obvious where to put the last edge. Also, considering $\sum_{v \in V} \deg(v) = 2m$, you can't do better than your graph given the restrictions you have to observe. $\endgroup$ – G. Bach Mar 23 '14 at 16:16
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

How to find solutions:

If you vary the number of vertices of degree 3, and the other constraint on the total number of edges or vertices, there is a simple way to find a minimal solution. You put your n compulsory edges of degree 3 in a circle, hence using two edges for each. Then, starting clockwise from some vertex, you connect the next vertex with degree 2 to the second neighbor clockwise if it also has degree 2, until you can no longer do it. This may leave you with one edge that will require adding a vertex of degree one, if n is odd. This is a solution with a minimal number of vertices and edges, but possibly not enough edges or vertices depending on required constraint. Then you start cutting edges in two with new vertices in between to reach the required number of vertices or edges. Each cut will add one edge and one vertex. You can also increase the number of vertices by two while increasing the number of edges by only one, if you cut an edge and use a different new vertex for the open end of each half.

Alternatively. If you already found a solution (possibly not minimal) to the problem as stated, you can always reduce the number of vertices if you have more than one vertex with degree one. You simply take two of them and merge them. If it cannot be done, that means that the solution is already minimal in the number of vertices.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.