1
$\begingroup$

I ran into a question in my textbook asking how many non-isomorphic simple graphs are there with 5 vertices and 3 edges, the answer says its 4, but I have no idea how I'm supposed to get that, there are also no examples of anything like this question either, I'm studying this for a midterm so I am much more interested in the process than the answer.

So I have a couple of confusions with this question. I tried to draw some graphs with v=5 and e=3 but stopped after like 3 after realizing there are so many graphs that are possible, am I really supposed to go through every single one and see if its isomorphic or not? also what am I even supposed check if its isomorphic to? I thought you needed 2 graphs to determine if they are isomorphic, What does it even mean to determine if one graph is isomorphic or not? Even when you have the 2 graphs you need to do a series of steps to check if they are even isomorphic right? The method we use right now is to check for equal edges, vertices, and series of degrees, and then we try to map each vertex to one on the other graph, if everything works it's isomorphic. Which in this case seems like it will take a very long time to do for all the possibilities. I don't think this question is supposed to be nearly as hard as I perceived. What am I missing here?

Furthermore how would I do this for other questions like this? for example 4 edges, 5 edges, 6 vertices, 7 vertices, etc. is there a series of steps I'm supposed to follow to solve a question like this?

$\endgroup$
  • $\begingroup$ my bad I got them confused I have edited my post $\endgroup$ – kek Feb 14 '17 at 0:59
  • 1
    $\begingroup$ The general problem here is almost certainly impossible to provide a useful answer for. In this specific case, because the number of edges and number of vertices is so small, you're certainly expected to do a case-by-case analysis. There must be at least one vertex shared between two edges (why?), so you just have to break down all the possibilities for the third edge. $\endgroup$ – Steven Stadnicki Feb 14 '17 at 1:00
  • $\begingroup$ You are wrong about "it will take a very long time". For $5$ vertices and $3$ edges, the time will be measured in seconds if you think about it right. Have you tried to do it? $\endgroup$ – bof Feb 14 '17 at 1:03
  • $\begingroup$ Start witn an easier one: how many nonisomorphic graphs with $5$ vertices and 1 edge? There are $\binom52=10$ places to put the edge so we have 10 graphs and we have to figure out which ones are isomorphic. There are $\binom{10}2=45$ pairs of graphs to test for isomorphism. For each pair, there are $5!=120$ bijections we have to check to see if they are isomorphisms . . . Thinking about it that way, it will take all day. The right way: the vertices are all the same, it doesn't matter where we put the edge, they are all isomorphic, the answer is 1. Now, what about 5 vertices and 2 edges? $\endgroup$ – bof Feb 14 '17 at 1:12
  • $\begingroup$ so are all the graphs non isomorphic? I tried to come up with the graphs for 5 vertices 3 edges and could only come up with 4 graphs that aren't the same. or am I just doing something wrong? $\endgroup$ – kek Feb 14 '17 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.