how many non-isomorphic graphs are there with 5 vertices and 3 edges?
How many non-isomorphic graphs with $5$ vertices and $3$ edges are there?
-
0if 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. – 2011-04-25
2 Answers
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.
- A graph with 3v of deg 2.
- A graph with 2v of deg 2, 2v of deg 1.
- 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.
-
0Nevermind, found the last one. 1v with deg 3, and 3v with deg 1. – 2011-12-01