# How many non-isomorphic graphs with $5$ vertices and $3$ edges are there?

how many non-isomorphic graphs are there with 5 vertices and 3 edges?

-
Draw a few pictures. Can't miss! –  André Nicolas Apr 24 '11 at 23:00
Which kinds of graphs are allowed? Why are you interested in this particular question? What have you tried? –  Rasmus Apr 24 '11 at 23:01
Is the homework problem just for a number? Anyway, try doing it for values less than 5 and 3 respectively. –  Mitch Apr 25 '11 at 0:27
if it is a simple graph, you can have three disjoint edges, two connected edges and 1 disjoint edge, three connected (not a triangle, not a star), a triangle, and a star. –  yoyo Apr 25 '11 at 20:53

Maybe ask a few easier questions.

How many non-isomorphic graphs with 5 vertices and 3 edges contain $K_3$ as a subgraph?

How many non-isomorphic graphs with 5 vertices and 3 edges are connected?

How many non-isomorphic graphs with 5 vertices and 3 edges have more than 2 connected components?

I agree with the comments that suggest you should draw pictures, try this for smaller values, and explain what you have tried so far. I'm hesitant to give a more complete answer since this seems likely to be a homework question.

-

The following are not isomorphic for sure.

1. A graph with 3v of deg 2.
2. A graph with 2v of deg 2, 2v of deg 1.
3. A graph with 1v of deg 2, 4v of deg 1.

As you can see further induction using the preservation of degree principle will not work, since the next stage would suggest 6v of deg 1 which violates the conditions.

My book answer suggests there is another graph, but I cannot find the last one, so I guess my logic is stuck somewhere, but I hope this helps so far.

-
Nevermind, found the last one. 1v with deg 3, and 3v with deg 1. –  Harry Dec 1 '11 at 8:48