2-factors in dense bipartite graphs Original Research Article

An n-ladder is a balanced bipartite graph with vertex sets A={a,…,an} and B={b1,…,bn} such that ai∼bj iff |i−j|⩽1. We use techniques developed recently by Komlós et al. (1997) to show that if G=(U,V,E) is a bipartite graph with |U|=n=|V|, with n sufficiently large, and the minimum degree of G is at least n/2+1, then G contains an n-ladder. This answers a question of Wang.