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.

  • $\begingroup$ v=9 is wrong, its 274668 $\endgroup$ – TROLLHUNTER Nov 29 '11 at 19:54
  • $\begingroup$ I take it you are enumerating the number of non-isomorphic graphs on $v$ vertices. You should spell this out in your question. $\endgroup$ – Austin Mohr Nov 29 '11 at 19:58
  • $\begingroup$ But any number of the form $v = 4n$ or $v = 4n+1$ has $max(e)/2$ an integer. So what's so special about 4? $\endgroup$ – Michael Lugo Nov 29 '11 at 20:36
  • 2
    $\begingroup$ Also, you might appreciate knowing that 4 really is special and this is not just a trick question. The number of non-isomorphic graphs on $v$ vertices is even for every $v \le 68$, except $v = 4$: abel.math.umu.se/~klasm/Data/numberofgraphs.txt . (As far as I know there's nothing special about 68; this is just the longest list I could find.) $\endgroup$ – Michael Lugo Nov 29 '11 at 20:39
  • $\begingroup$ OEIS gives first 19 values and also some formulas and references oeis.org/A000088 $\endgroup$ – Martin Sleziak Nov 29 '11 at 20:57

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
    $\begingroup$ 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). $\endgroup$ – Gerry Myerson Nov 29 '11 at 22:46

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.

  • 3
    $\begingroup$ Okay, but how does this distinguish $n = 4$ from $n = 5, 8, 9$? $\endgroup$ – Qiaochu Yuan Nov 29 '11 at 20:18
  • 1
    $\begingroup$ Well, it explains what's happening at $n=4$ and reduces the problem to counting self-complementary graphs. And it answers the question in the title. $\endgroup$ – Chris Godsil Nov 29 '11 at 21:08
  • 3
    $\begingroup$ I agree, Listing's answer doesn't give one any reason why $n = 4$ has an odd number of graphs at all. In fact, he just gives a formula, which isn't very instructive at all. +1 $\endgroup$ – GeoffDS Nov 29 '11 at 21:37
  • $\begingroup$ I agree that it explains something special about $n=4$ but it doesn't really explain why this property is unique to $n=4$, does it? $\endgroup$ – Listing Nov 29 '11 at 21:56
  • $\begingroup$ I was not criticizing Listing's answer, it is fine and more complete than what I wrote. $\endgroup$ – Chris Godsil Nov 29 '11 at 21:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.