number of edges in a graph whose vertices are binary strings

Question

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.

Answer 1

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.

Answer 2

Knowing the answer, it is easier to come up with direct proof that the number of edges is $n^2$. Intuitively, an edge "looks like" a contiguous sequence of $1$-s, with either the first or the last $1$ marked (corresponding to the position that is a $1$ in only one end vertex of the edge). We can encode this with the position of the two endpoints of the contiguous sequence, given in increasing order if the first position is marked and in decreasing order if the last position is marked.

Formally, let $v_{i,j}$ denote the string with $1$-s from the $i$-th position to the $j$-th position (inclusive) and $0$-s everywhere else, for any $1 \leq i < j \leq n$. Now for any pair $(i,j)$ with $1 \leq i,j \leq n$ we can assign an edge $e_{(i,j)}$ in the following way:

• if $i < j$, then let $e_{(i,j)}$ be the edge connecting $v_{i,j}$ with $v_{i+1,j}$;

• if $i = j$, let $e_{(i,j)}$ be the edge connecting $v_{i,j}$ with the all zero string;

• if $i > j$, let $e_{(i,j)}$ be the edge connecting $v_{j,i}$ with $v_{j,i-1}$.

It is not difficult to see that this gives a bijection between the edges of $G_n$ and the pairs $(i,j), 1 \leq i,j \leq n$.