---

Statement

Printed pp. 25--26, Section 1 ("The 7-cube minus a Hamming code"), read on the page images of the version of record named on the source card. The section has no theorem label; its results are the numbered properties (1) to (6) on p. 26, and this page is named for the section.

Setting (p. 25). The vertices of the hypercube on a set $I$ are the subsets of $I$, a vector space over $\mathbb F_2$ under symmetric difference $x+y$, with $x\sim y$ when $|x+y|=1$. Take $I=\mathbb Z_7$ and let $H$ consist of $\emptyset$, the seven sets $\{1+i,2+i,4+i\}$ ($i\in I$), and the complements of these eight sets. The paper states that $H$ is a subspace and a perfect $1$-error-correcting code, hence a Hamming code: its vertices are pairwise nonadjacent and every vertex outside $H$ has exactly one neighbor in $H$. The subgraph $\Gamma$ of the $7$-cube induced by $X=2^I\setminus H$ has $112$ vertices, is regular of valency $6$, and is vertex-transitive.

The coloring (pp. 25--26). For an edge $xy$ of $\Gamma$ with $x$ of odd weight, define $i,j\in I$ by $x+\{i\}\in H$ and $y=x+\{j\}$; the edge is red when $j-i\in\{1,2,4\}$ and white otherwise. $\Gamma_R$ and $\Gamma_W$ are the red and white subgraphs, both on the vertex set $X$.

Properties (p. 26). The paper states, with short indications for (1) to (3) and (6):

1. $\Gamma_R\cong\Gamma_W$; for odd-weight $u\in H$, $x\mapsto x+u$ is an isomorphism.
2. "$\mathrm{Aut}(\Gamma_R)=\mathrm{Aut}(\Gamma_W)$ is solvable of order 168, acts (sharply) transitively on the edges of both $\Gamma_R$ and $\Gamma_W$, and has two orbits on their vertex set $X$." The group is generated by the translations by members of the even-weight subcode $H_0$ of $H$, the cyclic shifts of $I$, and the permutation $i\mapsto2i$ of $I$.
3. "$\Gamma_R$ has diameter 8; for any vertex $x$ of odd weight there is a unique antipode $x+\{i,i+3,i+5,i+6\}$ at distance 8, where $i$ is determined by $x+\{i\}\in H$; no two vertices of even weight have distance 8."
4. Every quadrangle of $\Gamma$ has three edges of one color and one of the other. If $xy$ is a white edge, then $x$ and $y$ are at distance $3$ in $\Gamma_R$, joined there by a unique path $x\sim u\sim v\sim y$.
5. "$\Gamma_R$ has girth 10."
6. "$\Gamma_R$ is an 8-cover of the Heawood graph, the point-line incidence graph of the Fano plane." Identifying vertices of $\Gamma_R$ that differ by an element of $H_0$ gives a graph isomorphic to the Heawood graph on $I\cup I'$, with $i\sim j'$ if and only if $i-j\in\{1,2,4\}$.

So $\Gamma_R$ and $\Gamma_W$ are isomorphic cubic graphs of girth $10$ on $112$ vertices that are edge-transitive but not vertex-transitive, as the abstract (p. 25) puts it.

The three-coloring (p. 25). The paper notes that once both color classes have girth $10$, "it follows that the edges of $2^I$ can be colored with three colors such that there are no monochromatic $g$-gons for $g<10$." Section 3 (p. 28) recalls this as a three-coloring of the edges of the $n$-cube without monochromatic quadrangle or hexagon for $n\le7$.

Attribution and identification (pp. 26 and 28). The paper says the graph was constructed in Dejter and Guan (its reference [7]) and may be the graph R. M. Foster constructed according to Bouwer (reference [2]). A remark added in proof (p. 28) states that it differs from the unique trivalent graph on $112$ vertices with girth $10$ in Foster's census, since it is not vertex-transitive.

Source. A. E. Brouwer, I. J. Dejter and C. Thomassen, Highly symmetric subgraphs of hypercubes, J. Algebraic Combin. 2 (1993), 25--29, doi:10.1023/A:1022472513494; Section 1 on printed pp. 25--26, the remark added in proof on p. 28.

Read depth. Claims checked: the setting, the coloring and properties (1) to (6) were read clause by clause on the page images of printed pp. 25--26. The paper's indications of proof were read but not checked; properties (4) to (6) are stated without proof apart from the identification in (6).

Proof pointer

Pp. 25--26. Property (1) is witnessed by translation by an odd-weight codeword; for (2) the paper exhibits the group of order 168 and shows it is sharply edge-transitive, preserving the parity of the weight; (3) is verified by growing the distance classes from $x=\{1\}$ and $x=\{0,1\}$, which the paper says also shows that the full automorphism group is no larger than the group of (2); (6) is the quotient by $H_0$. Not checked here.

Dependencies

Self-contained; the facts that $H$ is a perfect code and a subspace are stated in the paper as standard.

Bears on

No Erdős problem directly. The three-coloring it yields for $n\le7$ is context for Section 3, whose four-coloring the paper uses against Erdős's hexagon conjecture.