2-factors in dense bipartite graphs (Q1850018): Difference between revisions

An \(n\)-ladder is a bipartite graph with vertex sets \(A=\{a_1,\dots,a_n\}\) and \(B=\{b_1,\dots,b_n\}\) such that \(a_i\) is adjacent with \(b_j\) if and only if \(|i-j|\leq 1\). In the paper it is proved that, if \(G=(U,V;E)\) is a bipartite graph with \(|U|=|V|=n\) for \(n\) sufficiently large, and the minimum degree of \(G\) is at least \(n/2+1\), then \(G\) contains an \(n\)-ladder. As a consequence, if a graph \(G\) satisfies the assumptions above, then every bipartite graph with \(n\) vertices in each part and maximum degree at most 2 is a spanning subgraph of \(G\).