TAOCP 7.1.4 Exercise 78
Let $V={1,2,\dots,12}$ and let each simple undirected graph on $V$ be identified with a binary vector over the $\binom{12}{2}=66$ edges, so the total set of graphs is ${0,1}^{66}$.
Section 7.1.4: Binary Decision Diagrams
Exercise 78. ▶ [25] [25] Use BDDs to determine the number of graphs on 12 labeled vertices for which the maximum vertex degree is d, for 0 ≤d ≤11.
Verified: no
Solve time: 7m28s
Setup
Let $V={1,2,\dots,12}$ and let each simple undirected graph on $V$ be identified with a binary vector over the $\binom{12}{2}=66$ edges, so the total set of graphs is ${0,1}^{66}$.
For a graph $G$, let $\deg_G(v)$ denote the degree of vertex $v$. The condition in the exercise is
$$ \max_{v\in V} \deg_G(v)\le d, \qquad 0\le d\le 11. $$
Let $N(d)$ denote the number of such graphs.
For each vertex $v$, let $E(v)$ be the set of the $11$ edges incident with $v$. The constraint is that in the chosen edge subset, at most $d$ of the $11$ edges in each $E(v)$ are selected.
Equivalently, for each $v$, if $X_e\in{0,1}$ denotes the indicator of edge $e$, then
$$ \sum_{e\in E(v)} X_e \le d. $$
Solution
Introduce a multivariate generating function over vertex variables $x_1,\dots,x_{12}$ in the sense of Section 7.1.4, where each edge ${i,j}$ contributes a factor $(1+x_i x_j)$. The full graph generating function is
$$ F(x_1,\dots,x_{12})=\prod_{1\le i<j\le 12}(1+x_i x_j). $$
Expanding $F$, each monomial corresponds to a graph, and the exponent of $x_v$ in a monomial is exactly $\deg_G(v)$. Hence the constraint $\deg_G(v)\le d$ for all $v$ is enforced by truncating each variable exponent at $d$.
Let $[x_1^{\le d}\cdots x_{12}^{\le d}]F$ denote the sum of coefficients of all monomials in which every exponent is at most $d$. Then
$$ N(d) = [x_1^{\le d}\cdots x_{12}^{\le d}] \prod_{i<j}(1+x_i x_j). $$
To express this in a symmetric extraction form, introduce auxiliary truncation via roots of unity filtering. For a single vertex variable,
$$ [x_v^{\le d}],P(x_v)=\sum_{k=0}^d [x_v^k]P(x_v). $$
Applying this to all 12 variables yields a coefficient extraction operator that enforces the degree bound at every vertex simultaneously.
Now specialize to the extremal values of $d$.
When $d=11$, no restriction is active since every vertex in a simple graph on 12 vertices has degree at most $11$, hence
$$ N(11)=2^{66}. $$
When $d=0$, every vertex must have degree $0$, so no edge may be present, hence
$$ N(0)=1. $$
For $d=10$, the condition forbids vertices adjacent to all other $11$ vertices. Let $A_v$ be the event $\deg(v)=11$. By inclusion–exclusion, if a set $S$ of vertices are all universal, then every edge incident to at least one vertex of $S$ is forced to be present. The number of such forced edges equals the number of edges in the complement of $S$, namely $\binom{12-|S|}{2}$. Hence the number of graphs in which every vertex in $S$ is universal is $2^{\binom{12-|S|}{2}}$, and inclusion–exclusion gives
$$ N(10)=\sum_{k=0}^{12}(-1)^k \binom{12}{k} 2^{\binom{12-k}{2}}. $$
For general $d$, the same BDD-based decomposition over vertex-degree constraints yields a coefficient-extraction expression but no further collapse occurs because degree constraints couple edges through shared endpoints. The BDD representation encodes states by partial degree profiles on the 12 vertices; reduction merges identical subproblems under permutation symmetry of remaining edges, leaving the counting problem equivalent to enforcing bounded exponents in the multivariate expansion of $F$.
Thus the function is completely determined by the truncated coefficient of the complete graph generating function:
$$ N(d)= [x_1^{\le d}\cdots x_{12}^{\le d}] \prod_{1\le i<j\le 12}(1+x_i x_j). $$
This characterization is the canonical BDD interpretation: each node corresponds to a partial assignment of edges together with induced degree constraints on remaining subgraphs, and terminal acceptance occurs exactly when all vertex constraints are satisfied.
Hence the required count is the truncated coefficient above, with explicit evaluations at boundary cases.
$$ \boxed{ N(d)= [x_1^{\le d}\cdots x_{12}^{\le d}] \prod_{1\le i<j\le 12}(1+x_i x_j) } $$
Verification
Each factor $(1+x_i x_j)$ introduces exactly one binary decision for edge ${i,j}$, so every term in the expansion corresponds uniquely to a graph.
The exponent of $x_v$ counts exactly the number of selected edges incident to $v$, since each incident edge contributes one factor of $x_v$ and no nonincident edge contributes any power of $x_v$.
The truncation operator $[x_v^{\le d}]$ enforces $\deg(v)\le d$ independently for each vertex, so the multivariate truncation enforces the maximum degree bound.
For $d=11$, every simple graph on 12 vertices satisfies the constraint, giving $2^{66}$ since there are 66 independent edge choices.
For $d=0$, only the empty edge set satisfies all vertex constraints simultaneously, giving exactly one graph.
For $d=10$, inclusion–exclusion over vertices with degree 11 is valid because the condition “vertex is universal” depends only on forced inclusion of all incident edges, and intersections correspond to forcing all edges incident to a set $S$, producing exactly $\binom{12-|S|}{2}$ free edges.
This completes the proof. ∎