Edge disjoint cycles through specified vertices

We give a sufficient condition for a simple graph G to have k pairwise edge‐disjoint cycles, each of which contains a prescribed set W of vertices. The condition is that the induced subgraph G [ W ] be 2 k ‐connected, and that for any two vertices at distance two in G [ W ], at least one of the two has degree at least | V ( G )|/2 + 2(k − 1) in G . This is a common generalization of special cases previously obtained by Bollobás/Brightwell (where k  = 1) and Li (where W  =  V ( G )). A key lemma is of independent interest. Let G be the complement of a bipartite graph with partite sets X , Y . If G is 2 k connected, then G contains k Hamilton cycles that are pairwise edge‐disjoint except for edges in G [ Y ]. © 2005 Wiley Periodicals, Inc. J Graph Theory