I just started learning graph theory and I had a question come to mind when drawing non-ismorphic graphs. Say you had a graph of order 5 with 6 edges, and the degrees of each node were as follows: $$3,2,2,2,1$$ There are two non-isormorphic graphs satisfying these conditions, which are

I was wondering if there was a way, given the order, edges, and degree counts, to find the number of non-isomorphic graphs of the same conditions. I tried looking at separate cases, but I'm not sure if I'm finding all of the correct non-isomorphic graphs. I thought about it for a while and thought I saw some empirical connections, but none of them panned out and I could not figure out a relationship between them.

  • 1
    $\begingroup$ This is partly the 'graph realisation' problem. Starting with a degree sequence (like 3,2,2,2,1) you ask if there is a graph that 'realises' that sequence. The order is just the size of the sequence, and the edges (for a simple graph) is the sum of the sequence. The difference here is that you want all graphs, and non-isomorphic ones at that. $\endgroup$ – gilleain Apr 28 at 11:01

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.