Silk Road Mathematics Competition

Remind that $n$-dimensional binary cube (boolean) is a graph with vertices labeled by binary sequences of length $n$, and there is an edge between any two vertices if and only if their sequences differ only in one corresponding coordinate (digit).

Then our problem is equivalent to the following: prove that if from a $10$-dimensional binary cube we remove $8$ edges, then we always obtain a hamiltonian graph (i.e., a graph having a hamiltonian cycle – a closed path passing through all vertices of the graph exactly once).

By induction on $n$ let's prove a more general statement: If from an $n$-dimensional binary cube, $n>1$, we remove arbitrary $(n-2)$ edges, then the obtained graph is hamiltonian.

Proof: For $n=2$ the statement is obvious, there is nothing to remove.

Assume that for $n=k>1$ the statement is true, and prove it for $n=k+1$.

Let $V=\{(a_0,a_1,\dots ,a_k):a_i\in \{0,1\},0\le i\le k\}$ be the set of vertices of the $(k+1)$-dimensional cube $C=⟨V,E⟩$, where $E$ is a set of edges. Let's take an arbitrary removed edge $e\in E$. W.l.o.g. we may assume that it connects vertices $u=(0,b_1,\dots ,b_k)$ and $v=(1,b_1,\dots ,b_k)$.

Then consider the sets of vertices $$V^0=\{(0,a_1,\dots ,a_k):a_i\in \{0,1\},1\le i\le k\}$$ and $$V^1=\{(1,a_1,\dots ,a_k):a_i\in \{0,1\},1\le i\le k\},$$ which form a partition of $V$; and corresponding subgraphs $C^0=⟨V^0,E\setminus V^0⟩$ and $C^1=⟨V^1,E\setminus V^1⟩$.

Note that: 1) Subgraphs $C^0$ and $C^1$ are identical to $k$-dimensional binary cubes; 2) A mapping $(0,a_1,\dots ,a_k){\to }^f(1,a_1,\dots ,a_k)$ is an isomorphism from $C^0$ to $C^1$.

Let $D\subset E$ be the set of all removed edges, $|D|=n-2=k-1$. Then we have a partition $D=D_0\cup D_1\cup D_2$, where $D_i$ is the set of edges removed from subgraph $C^i$, $i=0,1$, and $D_2$ is the set of removed edges which "connect" $C^0$ and $C^1$. In particular, $e\in D_2$.

Since $|f(D_0)\cup D_1|\le k-2$, then by the induction hypothesis in $C^1$ there is a hamiltonian cycle $v=v_1,v_2,\dots ,v_{2^k}$, which does not use the edges from $f(D_0)\cup D_1$. Then $u=u_1,u_2,\dots ,u_{2^k}$ is a hamiltonian cycle in $C^0$, where $f(u_i)=v_i$ for $1\le i\le 2^k$, not passing through the edges of $D_0$.

$$u=u_1,u_2,\dots ,u_i,v_i,v_{i-1},\dots ,v_1,v_{2^k},v_{2^k-1},\dots ,v_{i+1},u_{i+1},\dots ,u_{2^k}$$ is a hamiltonian cycle in $C$, not passing through the edges of $D$. The statement is proved. $\square$