Undergrad Explanation for parity difference for # of simple graphs

[Mr Davis 97]

http://oeis.org/A000088

This is a list that gives the number of simple graphs on n unlabeled vertices. Could someone conversant in graph theory explain why the number of simple graphs on 4 unlabeled vertices, which is 11, is the only one that seems to be odd (nontrivially), while the rest seem to be even?

 

[andrewkirk]

Is it possible that they are miscounting in the case n=4, missing an isomorphism between two of the cases?

I ask because I can only find ten cases:

1 case with 0 edges: {}
1 case with 1 edge: {12}
2 cases with 2 edges: {12, 34}, {12,23}
2 cases with 3 edges: {12, 23, 34}, {12, 23, 31}
2 cases with 4 edges: {12, 23, 34, 41}, {12, 23, 31, 14}
1 case with 5 edges: {12, 23, 34, 41, 13}
1 case with 6 edges: {12, 23, 34, 41, 13, 24}

Am I missing one? There are some that look different from the ones listed here, but are isomorphic to one of them. I thought my method was pretty thorough.

Given the impressive-looking list of references on the OEIS page, the weight of evidence suggests I've either missed one, or thought a relationship was isomorphic that wasn't..

 

[mfb]

You missed one case with three edges: 12,13,14

There is a symmetry between n edges and 6-n edges, so 3 is the only part that can lead to an odd result.

 

[Mr Davis 97]

You missed one case with three edges: 12,13,14

There is a symmetry between n edges and 6-n edges, so 3 is the only part that can lead to an odd result.

What makes the # of graphs on 4 vertices different than than the # of graphs on 5 vertices? For example, why isn't there an odd number of graphs with 5 vertices and 5 edges?

 

[mfb]

I don't know a mathematical argument, but you can still use the pairing for them. It turns out that exactly 2 (an even number) are their own partners.