Of course, take the complement and note that we are counting only connected graphs. Brendan. * David Wilson <davidwwilson at comcast.net> [050802 06:46]: > Oh, I see, it looks as if on 2k vertices, the number of k-regular graphs is one more than the number of k-1-regular graphs. This must have a nice proof?