Proving the number of coplanar subgraphs of a hypercube

Question

Given an n-dimensional hypercube, join each vertex to obtain a complete graph. Then the number of subgraphs of four coplanar vertices is given by

$6^n/8−4^{n−1}+2^{n−3}$

Example: a 2D square has just one coplanar rectangular subgraph, a 3D cube has 12 (6 faces and 6 connecting each diagonally opposite pair of edges).

How would I go about proving this result?

I've spent the last few days trying to find a proof for this, I only discovered this formula by computing the first few values with Matlab, and upon Googling this sequence led me to OEIS (sequence A016283), giving me this formula and confirming my suspicions via a brief comment, but I have been unable to find a formal proof for how this formula emerges from the problem.

(I don't have any much experience with graph theory so that's probably why I'm struggling to prove this myself, but this would be a nice result to include in something I'm writing.)

Answer 1

Let's first count the number of planar $K_4$'s with one vertex at the origin (assuming the vertices of the hypercube are at $\{0,1\}^n$).

If three of the vertices are at $\vec 0$, $\vec x$, and $\vec y$, then the entire plane containing them is given by $s \vec x + t \vec y$ with $s, t \in \mathbb R$. What can the fourth point be? There are two cases:

1. Suppose there are coordinates $i$ with $x_i = 1, y_i = 0$ and $j$ with $x_j=0, y_i = 1$. Then to get $sx_i + t y_i \in \{0,1\}$ we must have $s \in \{0,1\}$; to get $sx_j + ty_j \in \{0,1\}$ we must have $t \in \{0,1\}$. since $0\vec x + 0\vec y$, $0 \vec x + 1\vec y$, and $1\vec x + 0 \vec y$ are already counted, the fourth point must be $\vec x + \vec y$.
2. Suppose not there are not such coordinates; then without loss of generality, $\vec x \le \vec y$ in each coordinate. For $\vec x \ne \vec 0$, there needs to be a coordinate $i$ with $x_i = 1$ (and therefore $y_i=1$). For $\vec x \ne \vec y$, there needs to be a coordinate $j$ with $x_j=0$ and $y_j=1$. Now, to get $sx_i + ty_i \in \{0,1\}$ we must have $s=-t$ or $s=1-t$; to get $sx_j + ty_j \in \{0,1\}$ we must have $t \in \{0,1\}$. This is four possibilities, three of which are $\vec 0, \vec x, \vec y$; the fourth point must be $\vec y - \vec x$.

So we must have four vertices $\{0, \vec x, \vec y, \vec x + \vec y\}$ (the second case is just the same as the first with different vertices chosen as $\vec x$ and $\vec y$). To get $\vec x + \vec y \in \{0,1\}^n$, we cannot have $x_i = y_i = 1$ for any coordinate $i$.

This gives $3^n$ ways to choose $\vec x$ and $\vec y$: in each coordinate $i$, we choose either $x_i = y_i = 0$, or $x_i = 1, y_i=0$, or $x_i = 0, y_i = 1$. However, we must choose the second option at least once, and the third option at least once; otherwise, we get a degenerate set with $\vec x = \vec 0$ or $\vec y = \vec 0$. By inclusion-exclusion, the number of options is $3^n - 2^n - 2^n + 1^n$, or $3^n - 2 \cdot 2^n + 1$.

However, we get the same set $\{0, \vec x, \vec y, \vec x + \vec y\}$ if we swap $\vec x$ and $\vec y$, so there are only $\frac{3^n - 2 \cdot 2^n + 1}{2}$ planar $K_4$'s containing $\vec 0$.

---

There was nothing special about the origin, so there are also $\frac{3^n - 2 \cdot 2^n + 1}{2}$ planar $K_4$'s containing any other vertex. This gives a total of $2^n \cdot \frac{3^n - 2 \cdot 2^n + 1}{2} = \frac{6^n - 2 \cdot 4^n + 2^n}{2}$ planar $K_4$'s, except that each one is counted $4$ times: once for each of its vertices.

So the final answer is $$\frac{6^n - 2 \cdot 4^n + 2^n}{8}.$$