Set of vertices of graph $G$ is power set of $\{0,1,2,3,4,5,6,7,8,9\}$. Two vertices $A,B$ are connected iff $|A \Delta B |\le 2$. Then $|E(G)|=?$ 
Let the set of vertices of graph $G$ be the power set of $\{0,1,2,3,4,5,6,7,8,9\}$ and two (different) vertices $A,B$ are connected iff $|A \Delta B |\le 2$. How many edges does $G$ have?

I just need proof verification:

*

*If $|A\Delta B|=0$ then there is no edges.

*If $|A\Delta B|=1$ then there is ${10\choose 1}$ choises for $A\setminus B$ and $2^9$ for $A\cap B$ so we have $10\cdot 2^9$ edges.

*If $|A\Delta B|=2$ then we have 2 subcases:

*

*If $|A\setminus B| =2$ then there is ${10\choose 2}$ choises for $A\setminus B$ and $2^8$ for $A\cap B$ so we have $45\cdot 2^8$ edges.

*If $|A\setminus B| =1$ and $|B\setminus A| =1$ then there is ${10\choose 2}$ choises for $A\Delta B$ and $2^8$ for $A\cap B$ so we have again $45\cdot 2^8$ edges.



So we have overall $110\cdot 2^8$ edges?
 A: This looks right. I would add the preliminary statement for clarity:
For ensuring edges are only counted once, assume $|A|\geq|B|$
Then the rest follows

*

*If $|A\triangle B|=0$ then $A=B$ and there is no edge.

*If $|A\triangle B|=1$ then there are ${10\choose 1}$ choices for $A\setminus B$ and $2^9$ for $A\cap B$ so we have $10\cdot 2^9$ edges.

*If $|A\triangle B|=2$ then there are $2^8$ choices for $A\cap B$ and either:

*

*the ${10\choose 2}=45 $ choices for $A\triangle B$ are in $A$, giving $45\cdot 2^8$ edges or

*the ${10\choose 2}$ choices for $A\triangle B$ are split between $A$ and $B$ (at each end of an edge)  giving another $45\cdot 2^8$ edges



So a total of $55\cdot 2^9$ edes as you found.
A: Another method. First, note the number of ordered pairs $(A,B)$, where $A,B\subseteq [0,9]\cap \mathbb Z$ and $|A\Delta B|=k$, is $2^{10}\binom{n}k$. You choose the elements of $|A\cap B|$ in $\binom{n}k$ ways, and independently choose the subset $A$ in $2^{10}$ ways. The choice of $A\Delta B$ and $A$ determines $B$. Adding up $k=1$ and $k=2$, and dividing by two to get unordered pairs, you get $\frac12(2^{10}\binom{10}1+2^{10}\binom{10}2)$, agreeing with your answer.
