# A graph theory problem

• Jan 15th 2009, 09:57 AM
gusztav
A graph theory problem
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 $\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 $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 $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 find how many such graphs are there, just the number, and not to specifically draw each one, making the problem presumably easier?

Many thanks!
• Jan 15th 2009, 10:14 AM
Plato
These are called 'unlabled' graph of order 5.
You found the only two with the degree sequence <1,1,2,2,2>.
• Jan 15th 2009, 10:21 AM
gusztav
Quote:

Originally Posted by Plato
These are called 'unlabled' graph of order 5.
You found the only two with the degree sequence <1,1,2,2,2>.

Thanks a lot!

But now I wonder, how can I be sure that I have really found all of the graphs with the degree sequence <1,1,2,2,2> (up to an isomorphism) and that the "search" has been exhaustive?
• Jan 15th 2009, 11:08 AM
Plato
Do you know about graph cards?
You may find a website for them, I know of none.
Anyway I found them in GRAPHS by Wilson & Watkins.
The two graphs you found are the only to listed on the cards.