Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
14  
Draw a few pictures. Can't miss! –  André Nicolas Apr 24 '11 at 23:00
1  
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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer
    
Nevermind, found the last one. 1v with deg 3, and 3v with deg 1. –  Harry Dec 1 '11 at 8:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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