To clarify the concepts used: a bipartite partition of Graph G is a partition of the vertex set V into two disjoint vertex sets, say X and Y such that the union of X and Y is all of V and such that all internal edges within X and Y are deleted. The minimum degree of a graph is the smallest degree of any vertex.
So I was first thinking about a greedy strategy: that is, start with two vertices that have an edge and assign one to X and the other to Y, and then assign every other vertex to X or Y based on how many edges it has to those already in X and Y. (That is, given X and Y filled with vertices up to a certain point, pick v that hasn't been assigned and if it's minimum degree with vertices in X is smaller or equal than that in Y, put it in X, else in Y.). But I can't prove that this procedure will really yield the bipartite partition with highest minimum degree possible.
I was also thinking about using the characterization of bipartite graphs using odd cycles (A graph is bipartite iff it has no odd cycles) by removing one edge from each odd cycle, but that too I can't prove to yield the bipartite partition with highest minimum degree.
Is there a proven method for the goal I'm aiming for?
