Bipartiteness of hypercube graph with at least one edge contracted

Question

I am participating in a research in my university and as a side task I need to solve the following problem:

Consider a hypercube graph. Someone contracts one edge in it. What is the minimum number of edges more I need to contract to get bipartite graph again?

Is there any extensive theory about hypercube graphs to read so I can find a solution, because, for now, it is not that obvious for me. Or do you have any advises reagarding this problem?

Answer 1

I'll respond in terms of a request for references.

You might be interested in the Wikipedia article on edge contraction, as this notion seems to be more central to your problem than "hypercube graphs" per se.

A Google search finds this 2011 paper on "Obtaining a Bipartite Graph by Contracting Few Edges".

In the specific case you describe, an $n$-dimensional hypercube with one edge contracted, it is clear we can attain a bipartite graph by contracting $2^{n-1}-1$ additional edges of the original hypercube, those which were parallel to the first contracted edge.

So that gives an upper bound, but I don't know whether it is sharp. In that respect it is an interesting problem.