Explanation for parity difference for # of simple graphs

In summary, 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. This is because there is a symmetry between the number of edges and 6 minus the number of edges, which results in an even number for all cases except for 3 edges, which leads to an odd result. The difference between the number of graphs on 4 vertices and 5 vertices can be explained by the fact that there are exactly 2 graphs with 5 vertices and 5 edges that are their own partners, making the overall number an even number.
  • #1
Mr Davis 97
1,462
44
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?
 
Mathematics news on Phys.org
  • #2
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..
 
  • #3
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.
 
  • Like
Likes andrewkirk
  • #4
mfb said:
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?
 
  • #5
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.

graphs.png
 

Attachments

  • graphs.png
    graphs.png
    5.1 KB · Views: 316

1. What is the explanation for the difference in the number of simple graphs for odd and even numbers of vertices?

The explanation for this difference lies in the concept of parity, or the quality of being even or odd. When calculating the number of simple graphs, we must consider the number of possible edges that can be formed between vertices. For an odd number of vertices, there will always be an odd number of possible edges, while for an even number of vertices, there will be an even number of possible edges. This results in a difference in the number of simple graphs that can be formed.

2. Why does the difference in the number of simple graphs occur for odd and even numbers of vertices?

The difference in the number of simple graphs occurs because of the mathematical properties of even and odd numbers. An odd number of vertices will always have an odd number of possible edges, while an even number of vertices will have an even number of possible edges. This difference in the number of possible edges leads to a difference in the number of simple graphs that can be formed.

3. Is there a mathematical formula to calculate the number of simple graphs for odd and even numbers of vertices?

Yes, there is a formula to calculate the number of simple graphs for a given number of vertices. For odd numbers of vertices, the formula is (2^n-1)/2, where n is the number of vertices. For even numbers of vertices, the formula is (2^n/2) * (2^n-1), where n is the number of vertices.

4. Can you give an example to illustrate the difference in the number of simple graphs for odd and even numbers of vertices?

Sure, let's take the example of 3 vertices. For an odd number of vertices, there will be (2^3-1)/2 = 3 possible edges. These edges can be arranged in 3 different ways to form 3 simple graphs. Now, for an even number of vertices, let's take 4. There will be (2^4/2) * (2^4-1) = 16 possible edges, which can be arranged in 16 different ways to form 16 simple graphs. This shows the difference in the number of simple graphs for odd and even numbers of vertices.

5. How does understanding the difference in the number of simple graphs for odd and even numbers of vertices impact graph theory?

Understanding this difference is important in graph theory as it allows us to make predictions and prove theorems related to the properties of graphs. It also helps in analyzing and solving problems involving graphs. Additionally, this knowledge can be applied in various fields such as computer science, social networks, and transportation networks, where graphs are used to model real-world situations.

Similar threads

  • General Math
Replies
28
Views
2K
  • General Math
2
Replies
66
Views
4K
Replies
33
Views
4K
Replies
1
Views
527
  • General Math
Replies
2
Views
1K
  • General Math
Replies
2
Views
1K
  • High Energy, Nuclear, Particle Physics
Replies
7
Views
997
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
245
  • Introductory Physics Homework Help
Replies
4
Views
4K
Back
Top