16
$\begingroup$

I am working through Trudeau's Introduction to Graph Theory, which contains the following problem:

In the following table, the numbers in the second column are mostly even. If we ignore the first row on the ground that $v=1$ is such a trivial situation that its uniqueness is unremarkable, that leaves $v=4$ as the only number of vertices listed for which there are an odd number of graphs. Do you think this is due to chance, or can you think of some reason why $v=4$ should be unique?

  v    number of non-isomorphic graphs  1            1  2            2  3            4  4           11  5           34  6          156  7        1,044  8       12,346  9      308,708 

Note, this problem concerns the number of non-isomorphic graphs.

Here's what I have so far:

The maximum number of edges in a graph with $v=4$ is $\max(e)=\frac{1}{2}(v)(v-1)=\frac{1}{2}(4)(3)=6$. The graphs with $e=0,1,2,4,5,6$ come in pairs because each graph has a complement. So, there are an odd number of graphs with $v=4$ iff there are an odd number of graphs with $v=4$ and $e= \frac{\max(e)}{2}$.

There are 3 graphs with $v=4$ and $e= \frac{\max(e)}{2}=3$, so therefore there is an odd number of graphs with $v=4$.

However, I don't understand why $v=4$ should be special in this regard, even though it feels special.

  • 0
    OEIS gives first 19 values and also some formulas and references http://oeis.org/A0000882011-11-29

2 Answers 2

11

Definition: Let $g(n)$ denote the number of unlabeled graphs on $n$ vertices, let $e(n)$ denote its $2$-part, that is the largest power of $2$ which divides $g(n)$.

Lemma: If $n\geq5$ is odd then $e(n) = (n+1)/2-\lfloor \log_2(n) \rfloor$. If $n \geq 4$ is even then $e(n) \geq n/2 - \lfloor \log_2(n) \rfloor$ with equality iff $n$ is a power of $2$.

Corollary: The amount of unlabeled graphs is even for $n > 4$

Some values $e(\{4,5,\ldots,15\})=\{0,1,1,2,1,2,2,3,3,4,4,5\}$ (for even numbers it is the lower bound).

The theorem is due to Steven C. Cater and Robert W. Robinson and can be found, including a proof, in this publication.

They mention that $g(n)$ is not only even but contains a large number $2$'s in its prime factorisation for large $n$ (this also follows form the formula). In fact they even show that they are asymptotically $n/2$ factors of $2$ in $g(n)$.

  • 2
    The full citation for the paper is Steven C. Cater, Robert W. Robinson, Exponents of 2 in the numbers of unlabeled graphs and tournaments, Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Congr. Numer. 82 (1991), 139–155, MR1152066 (92k:05062).2011-11-29
4

If a graph on $n$ vertices has $e$ edges, then the number of edges in its complement is $ \frac{n(n-1)}{2} - e. $ So if if $n(n-1)/2$ is odd we can divide graphs in pairs (graph,complement), and then the number of graphs must be even. In particular the the parity of the number of isomorphism classes of graphs is equal to the parity of the number of isomorphism classes of self-complementary graphs. When $n=4$, the path is the unique self-complementary graph and the number of isomorphism classes is odd. Clearly when $n=6$ or $n=7$ there must be an even number of isomorphism classes self-complementary graphs.

  • 0
    I was not criticizing Listing's answer, it is fine and more complete than what I wrote.2011-11-29