COVERING A GRAPH WITH CYCLES PASSING THROUGH GIVEN EDGES

We propose a conjecture: for each integer k greater than or equal to 2 , there exists N(k) such that if G is a graph of order n greater than or equal to N(k) and d(x) + d(y) greater than or equal to n + 2k -2 fo r each pair of non adjacent vertices x and y of G, then for any k inde pendent edges e(1),...,e(k) of G, there exist k vertex-disjoint cycles C-1,...,C-k in G such that e(i) is an element of E(C-i) for all i E { 1,..., k} and V(C1U...UCk) = V(G). If this conjecture is true, the con dition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. (C) 1997 John Wiley & Sons, Inc.