We define the graph $G_n$ as follows. $V(G_n),$ the set of vertices of $G_n$, is the set of all binary strings of length $n$ with at most one block of $1$'s. Two vertices are adjacent iff they differ in exactly one position. Find the number of edges of $G_n$.
We let $E(G_n)$ denote the number of edges of $G_n.$ I know the number of vertices is ${n+2\choose 2}-{n+1\choose 2}+{n\choose 2},$ which can be found by determining the coefficient of $x^n$ in the generating series $\dfrac{1-x+x^2}{(1-x)^3}$ for the set of binary strings with at most one block of $1$'s. So I thought about listing all $2^n$ binary strings and all possible edges and subtracting out the ones with more than one block of $1$'s. There are $2^n – ({n+2\choose 2}-{n+1\choose 2}+{n\choose 2})$ strings of length $n$ with more than $1$ block of $1$'s, and each has $n$ neighbours (since there are $n$ ways to flip a bit in a binary string of length $n$) and thus it contributes $1$ to the degree of each of its $n$ neighbours. So one would think that the total contribution of the $2^n – ({n+2\choose 2}-{n+1\choose 2}+{n\choose 2})$ strings is $2n(2^n – ({n+2\choose 2}-{n+1\choose 2}+{n\choose 2}));$ the reason this is not the case is because this result may subtract extra degrees (e.g. $1001$ has a neighour of $1101,$ which is subtracted twice above, once for $1001$ and another time for $1101$). I know that to count the edges of a graph, it's usually best to find the degree sum, but I'm not sure how to find that in this case.
Best Answer
One somewhat tedious way is to categorize the vertices and count the number of edges coming out of the vertex.
$$\begin {array}{r r r} \text{string}&\text{count}&\text{number of edges}\\ \hline 0^n&1&n\\ 10^{n-1},0^{n-1}1&2&2\\ 1^s0^*,0^*1^s&2(n-2)&3\\ 0^*10^*&n-2&3\\ 0^*1^s0^*&\frac 12(n^2-5n+6)&4\\ 1^n&1&2 \end {array}$$ where a superscript $n$ means $n$ of these, $s$ means more than one of these, $*$ means at least one of these.
Multiplying the counts by the number of edges and adding gets $2n^2$ as the number of edges incident on all the vertices, so there are $n^2$ edges total.