Counting Graphs with a Prescribed Degree Sequence

Description of the problem

Here and here I dealt with the problem that whether a given non-increasing sequence of positive integers can be realized as the degree sequence of an undirected graph using Havel-Hakimi algorithm. Today, I’ll count the number of disctinct graphs with a fixed degree sequence.

The algorithm

By a graph I mean an undirected graph with no loops and no multiple edges. The algorith I am going to describe is recursive.

Function CountGraphs
Input: A degree sequence DS = (d_1,...,d_n)
Output: The number of distinct graph with DS as their degree sequence
Begin
  total <- 0
  For XS in the set of all subsets of {1,...,n-1} of size d_1
      ES <- (d_2,...,d_n)     
      For x in XS
          Reduce x-th term of ES by 1
      End For
      Sort ES and remove all 0's
      total <- total + CountGraphs(ES)
  End For
  Return total
End

Assume \((d_1\leq \cdots\leq d_n)\) is a degree sequence. We start with the first vertex. Since its degree is \(d_1\) we must connect it to \(d_1\) other vertices. In other words we must loop over all subsets of the index set \({1,\ldots,n-1}\) of size \(d_1\). By connecting the vertex to another vertex, we must reduce the degree of the connected vertex by 1. Thus, for every choice of connection, we get another degree sequence. Now, we proceed by recursion.

An implementation

Before I give my implementation, I am going to need few helper functions. I am going to need a function that returns the set of subsets of a certain size of a given set:

(defun subsets (k xs)
  (cond ((null xs) 'nil)
        ((= 1 k) (loop for x in xs collect (list x)))
        (t (union (subsets k (cdr xs))
                  (mapcar (lambda (x) (cons (car xs) x))
                          (subsets (1- k) (cdr xs)))))))

SUBSETS

Next, a helper function that performs the necessary reductions in degrees, sorting and removing zeros:

(defun new-degree-sequence (ds is)
  (let ((ys (copy-list ds)))
    (dolist (i is) (decf (nth i ys)))
    (delete 0 (sort ys #'<))))

NEW-DEGREE-SEQUENCE

Finally, our implementation. Notice the built-in memoization and the thread-last macro I stole from clojure:

(let ((table (make-hash-table :test #'equal)))
  (defun graph-count (ds)
    (cond
      ((equal ds '(1 1)) 1)
      ((< (length ds) 3) 0)
      ((oddp (reduce #'+ ds)) 0)
      (t (or (gethash ds table)
             (setf (gethash ds table)
                   (let ((es (cdr ds)))
                      (->> (loop for i from 0 below (length es) collect i)
                           (subsets (car ds))
                           (mapcar (lambda (x) (new-degree-sequence es x)))
                           (mapcar #'graph-count)
                           (reduce #'+)))))))))

GRAPH-COUNT

Tests

Let us start with \(K_5\) the complete graph on 5 vertices. The only graph with the degree sequence \((4,4,4,4,4)\) is \(K_5\).

(graph-count '(4 4 4 4 4))

1

The line graph \(A_5\) (a.k.a. Dynkin diagram of type \(A_5\)) has the degree sequence \((1,1,2,2,2)\). Including the permutations of the vertices of degree 2, there are 6 of them:

(graph-count '(1 1 2 2 2))

7

This threw me off at the beginning until I realize there is another graph with the same degree sequence: the disjoint union of \(A_2\) and the cycle graph on three vertices \(C_3\). So, the count is correct.

(graph-count '(1 1 1 1 1 1))

15

For this count, essentially we are counting the set of all subsets of size 2 of a set of size 6, which is \(\binom{6}{2}=15\).

Next, let us count the number of 3-regular graphs on 5 vertices:

(graph-count '(3 3 3 3 3))

0

This was a trick question: no such graph exists because of the hand-shake lemma which I put as one of the base cases in the recursion above. The smallest non-trivial 3-regular graph is \(K_4\). The next one must have at least 6 vertices:

(graph-count '(3 3 3 3 3 3))

70

Now finally, the count on a large sequence:

(graph-count '(1 1 1 1 1 1 1 2 2 3 3 3 4 4 5 7))

21065283747

Addendum

Using the algorithm above, I’ll count the number of of 2-regular graphs on \(n\) vertices from \(n=3\) to \(n=12\) below:

(loop for i from 3 to 12 collect
     (graph-count (loop repeat i collect 2)))

(1 3 12 70 465 3507 30016 286884 3026655 34944085)

This is the sequence A001205 at OEIS. Next is A002829 the the number of 3-regular graph on \(2n\) vertices from \(n=2\) to \(n=11\).

(loop for i from 2 to 11 collect
   (graph-count (loop repeat (* 2 i) collect 3)))

(1 70 19355 11180820 11555272575 19506631814670 50262958713792825
 187747837889699887800 976273961160363172131825 6840300875426184026353242750)

Continuing on to A005815 the number of 4-regular labeled graphs with n vertices.

(loop for i from 5 to 15 collect
     (graph-count (loop repeat i collect 4)))

(1 15 465 19355 1024380 66462606 5188453830 480413921130 52113376310985
 6551246596501035 945313907253606891)

And finally my own contribution to OEIS: A338978 the number of 5-regular labeled graphs with 2n vertices.

(loop for i from 3 to 14 collect
     (graph-count (loop repeat (* 2 i) collect 5)))

(1 3507 66462606 2977635137862 283097260184159421 52469332407700365320163
 17647883828569858659972268092 10148613081040117624319536901932188
 9494356410654311931931879706070629989407
 13859154719468565627065764000731047706917194485
 30467359843410315617245696171806527102000553683468790
 97852745740262121632666427672231508891042342116161424342990)