Long cycles in hypercubes with optimal number of faulty vertices

Let f(n) be the maximum integer such that for every set F of at most f(n) vertices of the hypercube Q n , there exists a cycle of length at least 2 ⁿ −2|F| in Q n −F. Castañeda and Gotchev conjectured that $f(n)=\left(\genfrac{}{}{0ex}{}{n}{2}\right)‐2$ . We prove this conjecture. We also prove that for every set F of at most (n ²+n−4)/4 vertices of Q n , there exists a path of length at least 2 ⁿ −2|F|−2 in Q n −F between any two vertices such that each of them has at most 3 neighbors in F. We introduce a new technique of potentials which could be of independent interest.