Find an example (as small as possible) of a graph with $6$ vertices of degree $3$ and other vertices with degree $\leq 2 $ with $12$ edges How can we find an example (as small as possible) of a graph with $6$ vertices of degree $3$ and other vertices with degree $\leq 2 $, with $12$ edges. Thank you.
 A: Since the graph must have $12$ edges, the sum of the degrees of the vertices must be twice that: $24$. Notice the $6$ vertices of degree $3$ contribute $18$, and thus we are still short by $24-18 = 6$. We are allowed to add vertices whose degree is at most $2$; in order to minimize the amount of vertices needed, we'll try to only add vertices whose degree is $2$. Since there are $6$ degrees left to account for, then we want $3$ vertices of degree $2$.
In order to arrange these vertices into a graph, I believe it is possible to construct a graph with the desired properties if the vertices of degree $3$ and the vertices of degree $2$ belong to two different connected components.
A: Just a graph that fits your requirement and is "as small as possible". A construction and calculation approach is already given by the other answers (@Andrei Kalunchakov, @benguin).

A: It turns out 9 vertices is the minimum possible.  It must be at least 9, since the number of edges (which equals 12) is half the sum of the degrees (by the Handshaking Lemma).  (With fewer than 9 vertices we have degree sum at most $3+3+3+3+3+3+2+2=22$, allowing only 11 edges.)
Using geng which comes with Nauty, we can generate all the $12$-edge $9$-vertex graphs, then filter out those with degree sequence $(3,3,3,3,3,3,2,2,2)$.  A simple example is $K_{3,3} \cup C_3$.
It turns out there are 68 non-isomorphic examples, and they are drawn below (with the vertices marked with their degrees):

A: Take a look at the Petersen's graph. 

Delete 3 successive outer edges. You will receive the second graph. It already satisfies your conditions.
But, as benguin stated in the answers, this is not minimal according to the number of vertices.
Denote $N$ as a number of vertices with degree $\le 2$. We have
$$12 \le \frac12\left(6\cdot3 + N\cdot 2\right).$$
So, we have $N \ge 3$.
Finally, note the two outer vertices could be merged and the resulted graph will be optimal.
