Extremal bipartite graphs with a unique k-factor

Given integers p > k > 0, we consider the following problem of extremal graph theory: How many edges can a bipartite graph of order 2p have, if it contains a unique k-factor? We show that a labeling of the vertices in each part exists, such that at each vertex the indices of its neighbours in the factor are either all greater or all smaller than those of its neighbours in the graph without the factor. This enables us to prove that every bipartite graph with a unique k-factor and maximal size has exactly 2k vertices of degree k and 2k vertices of degree |V (G)| 2 . As our main result we show that for k ≥ 1, p ≡ t (mod k), 0 ≤ t < k, ∗The results were proved while the author was working at the Lehrstuhl C für Mathematik, RWTH-Aachen. 182 A. Hoffmann, E. Sidorowicz and L. Volkmann a bipartite graph G of order 2p with a unique k-factor meets 2|E(G)| ≤ p(p + k)− t(k− t). Furthermore, we present the structure of extremal graphs.