How many graphs are there with five vertices, where the degrees of those five vertices are 1,1,2,2,2? I suppose we have to find the number of them up to an isomorphism.

If we use the theorem stating that the number of edges in a graph is half the sum of degrees of all vertices, we can see that every graph of the type we are looking for will have $\displaystyle \frac{1+1+2+2+2}{2}=4$ edges.

I have managed to find only two such graphs:

http://i42.tinypic.com/skw7dw.gif

In graph $\displaystyle G_1$, the vertices 1 and 5 are of degree 1, while vertices 2, 3, and 4 are of the degree 2, while in graph $\displaystyle G_2$, the vertices 1 and 2 are of degree 1, while vertices 3, 4, and 5 are of the degree 2.

How can I be sure there aren't more of such graphs? Is there an effective algorithm to find them? Actually, the problem asks to findhow manysuch graphs are there, just the number, and not to specifically draw each one, making the problem presumably easier?

Many thanks!