% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\newcommand{\D}{{\mathcal {D}}}
\def \Z {{\mathbb{Z}}}
\def \sq {{(2)}}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Decompositions of complete graphs\\ into bipartite $2$-regular subgraphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Darryn Bryant\thanks{Supported by the Australian Research Council via grants DP120103067, DP120100790, DP150100506, DP150100530.}\\
\small Department of Mathematics\\[-0.8ex]
\small University of Queensland\\[-0.8ex] 
\small QLD 4072, Australia\\
\small\tt db@maths.uq.edu.au\\
\and
Andrea Burgess\thanks{Supported by NSERC Canada through the Discovery Grant program.}\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small University of New Brunswick\\[-0.8ex] 
\small 100 Tucker Park Rd. P.O. Box 5050\\[-0.8ex]
\small Saint John, New Brunswick\\[-0.8ex]
\small E2L 4L5, Canada\\
\small\tt andrea.burgess@unb.ca\\
\and
Peter Danziger\thanks{Supported by NSERC Canada through the Discovery Grant program.}\\
\small Department of Mathematics\\[-0.8ex]
\small Ryerson University\\[-0.8ex]
\small Toronto, Ontario\\[-0.8ex]
\small M5B 2K3, Canada\\
\small\tt danziger@ryerson.ca
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Aug 26, 2014}{Feb XX, 2016}\\
\small Mathematics Subject Classifications: 05C51, 05C70, 05B30}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  It is shown that if $G$ is any bipartite $2$-regular graph of order at most $\frac n2$ or at least $n-2$, then the obvious necessary conditions are sufficient for the existence of a decomposition of the complete graph of order $n$ into a perfect matching and edge-disjoint copies of $G$. 

  % keywords are optional
%  \bigskip\noindent \textbf{Keywords:} graph reconstruction
%  conjecture; Broglington manifold; Pipletti's classification
\end{abstract}

\section{Introduction}

A {\em decomposition} of a graph $K$ is a set $\{G_1,G_2,\ldots,G_t\}$ of subgraphs of $K$ such that 
$E(G_1)\cup E(G_2)\cup \cdots\cup E(G_t)=E(K)$ and
$E(G_i)\cap E(G_j)=\emptyset$ for $1\leq i<j\leq t$.
If $G$ is a fixed graph and $\D=\{G_1,G_2,\ldots,G_t\}$ is a decomposition such that 
$G_i$ is isomorphic to $G$ for $i=1,2,\ldots,t$, then $\D$ is called a {\em $G$-decomposition}.
See \cite{BryElz} for a survey on $G$-decompositions, and see \cite{BarKuhLoOst,Wil} for general asymptotic existence results. 

This paper concerns $G$-decompositions of complete graphs in the case where $G$ is a  
$2$-regular graph. See \cite{AdaBryBuc} for a survey of results on $G$-decompositions of complete graphs. 
The complete graph of order $n$ is denoted by $K_n$, the cycle of order $n$ is denoted by $C_n$, and 
the path of order $n$ is denoted by $P_n$ (so $P_n$ has $n-1$ edges). 
If $G$ is $2$-regular and $n$ is even, then there is no $G$-decomposition 
of $K_n$, and it is common to instead consider decompositions 
of $K_n-I$, where $K_n-I$ denotes the graph obtained from $K_n$ by deleting the 
edges of a perfect matching. 
For each positive integer $n$, define $K_n^*$ to be $K_n$ if $n$ is odd and $K_n-I$ if $n$ is even.
The number of edges in $K_n^*$ is given by $n\lfloor\frac{n-1}2\rfloor$.

If $G$ is a $2$-regular graph of order $k$ and there exists a $G$-decomposition of $K_n^*$ ($n\geq 3$), 
then it is obvious that 
\begin{equation}\label{onc}
3\leq k\leq n\quad{\rm ~and~}\quad k {\rm ~divides~} n\textstyle\lfloor\frac{n-1}2\rfloor.
\end{equation}
If $G$ is a $2$-regular graph of order $k$, 
then the conditions given in (\ref{onc}) are called 
{\em the obvious necessary conditions} for the existence 
of a $G$-decomposition of $K_n^*$.
The following problem presents itself.

\vspace{0.3cm}

\noindent{\bf Problem 1:} 
{\it 
For each $2$-regular graph $G$ and each positive integer $n$ satisfying the obvious 
necessary conditions, 
determine whether there exists a $G$-decomposition of $K_n^*$.
}

\vspace{0.3cm}

It is known that if $G$ is a cycle, then the obvious necessary conditions are sufficient for the existence of a $G$-decomposition of $K_n^*$  \cite{AlsGav,Saj}. However, when $G$ is $2$-regular but is not a cycle, there are cases where the obvious necessary condition are satisfied but no $G$-decomposition of $K_n^*$ exists.  
There is no $G$-decomposition of $K_n^*$ in each of the following cases (see \cite{BryElz} and \cite{BryRod}).
$$
\begin{array}{lll}
G=C_3\cup C_3{\rm ~and~}n=6,\hspace{0.5cm}&G=C_3\cup C_3{\rm ~and~}n=9,\hspace{0.5cm}&G=C_4\cup C_5{\rm ~and~}n=9,\hspace{0.5cm}\\
\end{array}
$$
$$
\begin{array}{ll}
G=C_3\cup C_3\cup C_5{\rm ~and~}n=11,\hspace{0.5cm}&G=C_3\cup C_3\cup C_3\cup C_3{\rm ~and~}n=12.\hspace{0.5cm}\\
\end{array}
$$
If $G$ has order $n$, then Problem 1 is precisely the well-known Oberwolfach Problem. 
See \cite{BryRod,BrySch,Tra} for more information on the Oberwolfach Problem, and see \cite{CioCam} for a generalisation of the problem. 

Problem 1 has been solved
for every $2$-regular graph of order at most $10$ when $n$ is odd \cite{AdaBryGav},
and various results on Problem 1  
have been obtained via graph labellings. For example, in \cite{AguElzHakStoYay} it is shown that if 
$G$ has order $k$ and is $2$-regular with at most three components, 
then there exists a $G$-decomposition of $K_{2k+1}$, and in \cite{BliElz} it is shown that if $G$ is bipartite and $2$-regular of order $k$, then there exists a $G$-decomposition of $K_{2kx+1}$ for each positive integer $x$.
Several strong results have also been obtained on Problem 1 for the case where $G$ consists of 
disjoint $3$-cycles \cite{ColHorWan1,ColHorWan2}. These results relate to {\em Kirkman signal sets} which are are used in devising codes for unipolar communication, see \cite {ColZha}.
 
In \cite{Hag}, a simple but powerful idea is used to show that 
if both $n$ and ${n\lfloor\frac{n-1}2\rfloor}/k$ are even, then
there is a $G$-decomposition of $K_n^*$ 
for every bipartite $2$-regular graph $G$ of order $k$. 
Our main result, see Theorem \ref{mainthm}, extends this result
to the case ${n\lfloor\frac{n-1}2\rfloor}/k$ is odd, except when
$\frac n2<k<n-2$.
The special case of this extension where $k=n$ (that is, the case corresponding to the Oberwolfach Problem) is the main result in \cite{BryDan}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Notation and Preliminary Results}

For a given graph $K$, we define the graph $K^\sq$ by 
$V(K^\sq)=V(K)\times\Z_2$ and 
$E(K^\sq)=\{\{(x,a),(y,b)\}:\{x,y\}\in E(K),\ a,b\in\Z_2\}$. 
If $\mathcal F=\{G_1,G_2,\ldots,G_t\}$ is a set of graphs
then we define $\mathcal F^\sq=\{G_1^\sq,G_2^\sq,\ldots,G_t^\sq\}$. 
Observe that if $\mathcal F$ is a decomposition of $K$, then 
$\mathcal F^\sq$ is a decomposition of $K^\sq$.

The following result of H\"{a}ggkvist \cite{Hag} is a critical ingredient in many of our constructions. 

\begin{theorem} {\rm (H\"{a}ggkvist \cite{Hag})}\label{HaggPathLemma}
If $G$ is a bipartite $2$-regular graph of order $2m$,
then there is a $G$-decomposition of $P_{m+1}^\sq$.
\end{theorem}

Parker \cite{Par} has completely settled the problem of decomposing complete bipartite graphs into paths of uniform length, and we need the following special case of her result. 

\begin{theorem} {\rm (Parker \cite{Par})}\label{ParkerTheorem}
If $r$ and $a$ are even with $r\leq 2a-2$, $r\leq 2b$, and $r$ dividing $ab$, then there is a $P_{r+1}$-decomposition of $K_{a,b}$.
\end{theorem}

We also need the following result of Tarsi on decompositions of complete graphs into isomorphic paths \cite{Tar}.

\begin{theorem} {\rm (Tarsi \cite{Tar})}\label{TarsiTheorem}
There is a $P_{r+1}$-decomposition of $K_v$ if and only if $v\geq r+1$ and $r$ divides $v(v-1)/2$.
\end{theorem}

For each even $r\geq 2$, let $Y_r$ denote any graph isomorphic to 
the graph with vertex set 
$\{v_1,v_2,\ldots,v_{r+1}\}$
and edge set  
$$\{v_iv_{i+1}:i=1,2,\ldots,r\}
\cup\{v_1v_3\}
\cup\{v_iv_{i+3}:i=2,4,\ldots,r-2\}$$
($E(Y_2)=\{v_1v_2,v_2v_3,v_1v_3\}$),
and let $X_{2r}$ denote the graph 
obtained from $Y_r^\sq$ by adding the edges 
$\{(v_1,0),(v_1,1)\},\{(v_2,0),(v_2,1)\},\ldots,\{(v_{r+1},0),(v_{r+1},1)\}$.

\begin{lemma}\label{intopathsandym}
For each even $r\geq 2$, there exists a decomposition of $K_{r+1}$ into $\frac{r-2}2$ 
Hamilton paths and a copy of $Y_r$.
\end{lemma}

\begin{proof}
Let $r\geq 2$ be even 
and for $i=0,1,\ldots,r$ 
let $M_i$ be the matching with edge set
$\{\{x,y\}:x\neq y, x+y=i\}$
in the complete 
graph with vertex set $\Z_{r+1}$. 
Then 
$$\{M_0\cup M_1\cup M_2,
M_3\cup M_4,M_5\cup M_6,
\ldots,M_{r-1}\cup M_{r}\}$$
is the required decomposition.
\end{proof}

\begin{lemma}\label{HoleLemma}
If $r$ is even, $2\leq r\leq\frac{m-1}2$, and $r$ divides $\frac 12m(m-1)-\frac {3r}2$, then there is a $P_{r+1}$-decomposition of $K_m-Y_r$.
\end{lemma}

\begin{proof}
By Lemma \ref{intopathsandym}, there is a $P_{r+1}$-decomposition of $K_{r+1}-Y_r$, so it suffices to show that there is a $P_{r+1}$-decomposition of $K_m-K_{r+1}$. But $K_m-K_{r+1}$ can be decomposed into $K_{r,m-r-1}$ and $K_{m-r}$, so it suffices to prove that $K_{r,m-r-1}$ and $K_{m-r}$ each have $P_{r+1}$-decompositions. The former has a $P_{r+1}$-decomposition by Theorem \ref{ParkerTheorem}, and the latter by Theorem \ref{TarsiTheorem}. It is routine to check that the hypotheses of these two theorems are satisfied when
$r$ is even, $2\leq r\leq\frac{m-1}2$ and $r$ divides $\frac 12m(m-1)-\frac {3r}2$.
\end{proof}

For each even $r\geq 2$ we define the graph $J_{2r}$ (see Figure \ref{J_r}) to be 
the graph with vertex set
$$V(J_{2r})=\{u_1,u_2,\ldots,u_{r+2}\}\cup\{v_1,v_2,\ldots,v_{r+2}\}$$
and edge set
$$
\begin{array}{rl}
E(J_{2r})=
&\{\{u_i,v_i\}:i=3,4,\ldots,r+2\}\ \cup\\
&\{\{u_i,u_{i+1}\},\{v_i,v_{i+1}\},\{u_i,v_{i+1}\},\{v_i,u_{i+1}\}:
i=2,3,\ldots,r+1\}\ \cup\\
&\{\{u_i,u_{i+3}\},\{v_i,v_{i+3}\}\{u_i,v_{i+3}\},\{v_i,u_{i+3}\}:
i=1,3,\ldots,r-1\}.\\
\end{array}
$$

\setlength{\unitlength}{.9pt}
\begin{figure}[htb]
\begin{center}
\begin{picture}(420,100)(0,-30)
\multiput(0,0)(0,50){2}{\multiput(0,0)(50,0){5}{\circle*{5}}}
\multiput(230,25)(10,0){3}{\circle*{2}}
\multiput(280,0)(0,50){2}{\multiput(0,0)(50,0){4}{\circle*{5}}}
\thicklines
% Verticals
\multiput(0,0)(230,0){2}{
    \multiput(100,0)(50,0){3}{\line(0,1){50}}
}
\put(280,0){\line(0,1){50}}
% Distance 1
\multiput(50,0)(0,50){2}{\multiput(0,0)(210,0){2}{\line(1,0){170}}}
% Distance 1 cross
\multiput(0,0)(230,0){2}{
    \multiput(50,0)(50,0){3}{\line(1,1){50}}
    \multiput(50,50)(50,0){3}{\line(1,-1){50}}
    \multiput(50,0)(50,0){3}{\line(1,1){50}}
}
\multiput(200,50)(60,-30){2}{\line(1,-1){20}}
\multiput(200,0)(60,30){2}{\line(1,1){20}}
% Distance 3 cross
\multiput(0,0)(280,0){2}{
    \put(0,0){\line(3,1){150}}
    \qbezier(0,50)(75,75)(150,50)
    \qbezier(0,0)(75,-25)(150,0)
    \put(0,50){\line(3,-1){150}}
}
\put(200,50){\line(3,1){20}}
\put(200,50){\line(3,-1){20}}
\put(200,0){\line(3,-1){20}}
\put(200,0){\line(3,1){20}}
%
\qbezier(100,50)(175,75)(220,60)
\put(100,50){\line(3,-1){120}}
\qbezier(100,0)(175,-25)(220,-10)
\put(100,0){\line(3,1){120}}
\qbezier(330,50)(300,60)(260,60)
\put(330,50){\line(-3,-1){70}}
\qbezier(330,0)(300,-10)(260,-10)
\put(330,0){\line(-3,1){70}}
% Labels
\put(0,70){\makebox(0,0){\small $u_1$}}
\put(50,70){\makebox(0,0){\small $u_2$}}
\put(100,70){\makebox(0,0){\small $u_3$}}
\put(150,70){\makebox(0,0){\small $u_4$}}
\put(200,70){\makebox(0,0){\small $u_5$}}
\put(280,70){\makebox(0,0){\small $u_{r-1}$}}
\put(330,70){\makebox(0,0){\small $u_{r}$}}
\put(380,70){\makebox(0,0){\small $u_{r+1}$}}
\put(430,70){\makebox(0,0){\small $u_{r+2}$}}
\put(0,-30){\makebox(0,0){\small $v_1$}}
\put(50,-30){\makebox(0,0){\small $v_2$}}
\put(100,-30){\makebox(0,0){\small $v_3$}}
\put(150,-30){\makebox(0,0){\small $v_4$}}
\put(200,-30){\makebox(0,0){\small $v_5$}}
\put(280,-30){\makebox(0,0){\small $v_{r-1}$}}
\put(330,-30){\makebox(0,0){\small $v_{r}$}}
\put(380,-30){\makebox(0,0){\small $v_{r+1}$}}
\put(430,-30){\makebox(0,0){\small $v_{r+2}$}}
\end{picture}
\caption{The graph $J_{2r}$}\label{J_r}
\end{center}
\end{figure}

The following result is proved in \cite{BryDan}, see Lemma 10 and the proof of Lemma 11.

\begin{lemma}\label{JdecompsLemma}
If $G$ is a bipartite $2$-regular graph of order $2r$ where $r\geq 4$ is even, then there is a decomposition $\{H_1,H_2,H_3,H_4\}$ of $J_{2r}$ such that 
\begin{itemize}
\item [(1)] $V(H_1)=\{u_1,u_2,\ldots,u_r\}\cup\{v_3,v_4,\ldots,v_{r+2}\}$, 
\item [(2)] $V(H_2)=\{u_3,u_4,\ldots,u_{r+2}\}\cup\{v_1,v_2,\ldots,v_r\}$, 
\item [(3)] $V(H_3)=\{u_3,u_4,\ldots,u_{r+2}\}\cup\{v_3,v_4,\ldots,v_{r+2}\}$, 
\item [(4)] $V(H_4)=\{u_3,u_4,\ldots,u_{r+2}\}\cup\{v_3,v_4,\ldots,v_{r+2}\}$,
\item [(5)] each of $H_1$, $H_2$ and $H_3$ is isomorphic to $G$,
\item [(6)] $H_4$ is a $1$-regular graph of order $2r$.
\end{itemize}
\end{lemma}

\begin{lemma}\label{Xmdecomps}
If $r\geq 2$ is even and $G$ is any bipartite 
$2$-regular graph of order $2r$,
then there is a decomposition of 
$X_{2r}$ into three copies of $G$
and a $1$-factor.
\end{lemma}

\begin{proof}
If $r=2$, then $G$ is a $4$-cycle, $X_{2r}$ is isomorphic to $K_6$ and the result holds. 
So assume $r\geq 4$.
Observe that if the edges $\{u_1,u_4\},\{u_1,v_4\},\{v_1,u_4\},\{v_1,v_4\}$
of $J_{2r}$ are replaced with $\{u_2,u_4\},\{u_2,v_4\},\{v_2,u_4\},\{v_2,v_4\}$, the vertices
$u_1$ and $v_1$ are deleted, and the edge $\{u_2,v_2\}$ is added, then the resulting graph is $X_{2r}$.
Let $\{H_1,H_2,H_3,H_4\}$ be the decomposition of $J_{2r}$ given by Lemma \ref{JdecompsLemma},
let $H'_1$ be the graph obtained from $H_1$ by replacing the edges $\{u_1,u_4\}$ and $\{u_1,v_4\}$ with 
$\{v_2,u_4\}$ and $\{v_2,v_4\}$,
let $H'_2$ be the graph obtained from $H_2$ by replacing the edges $\{v_1,u_4\}$ and $\{v_1,v_4\}$ with 
$\{u_2,u_4\}$ and $\{u_2,v_4\}$, let $H'_3=H_3$ and let $H'_4$ be the graph obtained from $H_4$ by adding the edge $\{u_2,v_2\}$ (and the vertices $u_2$ and $u_4$). 
It is easy to see that $\{H'_1,H'_2,H'_3,H'_4\}$ is the required decomposition of $X_{2r}$. 
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Main Results}

\begin{lemma}\label{k=n-2case}
If $n\geq 6$ is even and $G$ is any 
bipartite $2$-regular graph of order 
$n-2$, then there is a $G$-decomposition of 
$K_n-I$.
\end{lemma}

\begin{proof}
Let $m=\frac n2$. If $m$ is even, then let
$\D$ be a decomposition of $K_m$ into 
$\frac m2$
Hamilton paths, and if $m$ is odd, then
let $\D$ be a decomposition of $K_m$ into
$\frac{m-3}2$ 
Hamilton paths and a copy of $Y_{m-1}$.
The first of these decompositions exists by Theorem \ref{TarsiTheorem} and the second exists by 
Lemma \ref{intopathsandym}.
In either case let the vertex set of $K_m$ 
be $\Z_m$ and 
let $I$ be the $1$-regular graph with 
$V(I)=\Z_m\times\Z_2$ and edge set
$E(I) = \{(v, 0)(v, 1): v \in \Z_m\}$.

Thus, $\D^\sq\cup\{I\}$ is a decomposition of
$K_n$ into $\frac m2$ copies of $P_m^\sq$ and 
the  
perfect matching $I$ when $m$ is even, and is 
a decomposition of
$K_n$ into $\frac {m-3}2$ copies of $P_m^\sq$, 
one copy of $Y_{m-1}^\sq$, and the 
perfect matching $I$ when $m$ is odd.
Since the union of the copy of $Y_{m-1}^\sq$ 
and $I$ 
is a copy of $X_{n-2}$, the result 
follows by Theorem \ref{HaggPathLemma} and Lemma 
\ref{Xmdecomps}. 
\end{proof}

\begin{lemma}\label{mainconstructionlemma}
Let $r\geq 2$. 
If there is a $P_{r+1}$-decomposition of $K_m$ or 
if $r$ is even and there is a $P_{r+1}$-decomposition of $K_m-Y_r$, 
then there is a $G$-decomposition of $K_{2m}-I$ for every bipartite $2$-regular graph of order $2r$.
\end{lemma}

\begin{proof}
Let $G$ be a bipartite $2$-regular graph of order $2r$, let the vertex set of $K_m$ 
be $\Z_m$ and 
let $I$ be the $1$-regular graph with 
$V(I)=\Z_m\times\Z_2$ and edge set
$E(I) = \{(v, 0)(v, 1): v \in \Z_m\}$.

If there is a $P_{r+1}$-decomposition $\D$ of $K_m$, then $\D^\sq$ is a $P_{r+1}^\sq$-decomposition 
of $K_{2m}-I$. By Theorem \ref{HaggPathLemma}, we can decompose each copy of $P_{r+1}^\sq$ in $\D^\sq$ into two copies of $G$, thereby obtaining a $G$-decomposition of $K_{2m}-I$.

Thus, we can assume $r$ is even and there is a $P_{r+1}$-decomposition of $K_m-Y_r$, and hence a decomposition $\D$ of $K_m$ into one copy of $Y_r$ and $(\binom m2-\frac {3r}2)/r$ copies of $P_{r+1}$. It follows that $\D^\sq\cup\{I\}$ is a decomposition of $K_{2m}$ into one copy of $Y_r^\sq$, $(\binom m2-\frac {3r}2)/r$ copies of $P_{r+1}^\sq$, and a perfect matching. 
There are $r+1$ edges of $I$ which form a $1$-regular graph on the vertex set of the copy of $Y_r^\sq$, and the union of this $1$-regular graph with the copy of $Y_r^\sq$ is a copy of $X_{2r}$. 
Thus, we have a decomposition of $K_{2m}$ into one copy of $X_{2r}$, $(\binom m2-\frac {3r}2)/r$ copies of $P_{r+1}^\sq$, and a matching $M$ with $m-(r+1)$ edges (such that $M$ and the copy of $X_{2r}$ are vertex-disjoint). 

By Theorem \ref{HaggPathLemma}, we can decompose each copy of $P_{r+1}^\sq$ in $\D^\sq$ into two copies of $G$. Let $\D_P$ be the union of all of these decompositions. 
By Lemma \ref{Xmdecomps}, there is a decomposition $\D_X\cup\{M'\}$ of the copy of $X_{2r}$ where $\D_X$ contains three copies of $G$ and $M'$ is a perfect matching in the copy of $X_{2r}$. This means that the union of $M$ and $M'$ is a perfect matching in $K_{2m}$. It follows that $\D_P\cup\D_X$ is a $G$-decomposition of $K_{2m}-I$.
\end{proof}

\begin{theorem}\label{mainthm}
Let $G$ be a bipartite $2$-regular graph, let $k$ be the order of $G$, and let $n\geq 4$ be even.
There exists a $G$-decomposition of $K_n-I$ if and only if 
$3\leq k\leq n$ and $k$ divides $\frac{n(n-2)}2$,
except possibly when $\frac n2<k<n-2$ and $\frac{n(n-2)}{2k}$ is odd both hold.
\end{theorem}

\begin{proof}
The conditions $3\leq k\leq n$ and $k$ divides $\frac{n(n-2)}2$ are clearly necessary for the existence of a $G$-decomposition of $K_n-I$. The case $k=n$ is covered by the main theorem in \cite{BryDan}
and the case $k=n-2$ is covered by Lemma \ref{k=n-2case}. If $k=n-1$, then $k$ does not divide $\frac{n(n-2)}2$ so there is nothing to prove.
Thus, it remains only to show that there is a $G$-decomposition of $K_n-I$ when 
$3\leq k\leq \frac n2$ and $k$ divides $\frac{n(n-2)}2$.

Let $m=\frac n2$ and let $r=\frac k2$ (since $G$ is bipartite, $k$ is even and $r\geq 2$ is an integer). 
By Lemma \ref{mainconstructionlemma}, it suffices to show that there is a $P_{r+1}$-decomposition of $K_m$ or that $r$ is even and there is a $P_{r+1}$-decomposition of $K_m-Y_r$. If $2m(m-1)/k$ is even, then $r$ divides $m(m-1)/2$ and so by Theorem \ref{TarsiTheorem}, there is a $P_{r+1}$-decomposition of $K_m$. If $2m(m-1)/k$ is odd, then it follows that $r$ is even, $r$ divides $\frac 12m(m-1)-\frac {3r}2$, and $k\neq m$. So $r\leq\frac{m-1}2$ and there is a $P_{r+1}$-decomposition of $K_m-Y_r$ by Lemma \ref{HoleLemma}. 
\end{proof}

Lemma \ref{mainconstructionlemma} gives a possible approach to settling the possible exceptions in 
Theorem \ref{mainthm}. The missing ingredient is $P_{r+1}$-decompositions of 
$K_m-Y_r$ for $\frac m2<r<m-1$ where $r=\frac k2$ and $m=\frac n2$.
The first few possible exceptions in Theorem \ref{mainthm} are 
$(k,n)=(12,20)$, $(20,30)$, $(24,42)$, $(28,44)$, $(36,54)$, $(40,72)$, $(44,68)$, $(48,80)$, $(52,78)$, 
$(56,72)$, $(60,92)$, $(60,102)$ and $(60,110)$.

It is worth remarking 
that the constructions used to prove Theorem \ref{mainthm} can be easily generalised as follows.
In the proof of Lemma \ref{mainconstructionlemma}, each copy of 
$P_{r+1}^\sq$ can be decomposed independently, resulting in decompositions of $K_n-I$ into $2$-regular graphs which are not all isomorphic. Although each copy of $P_{r+1}^\sq$ produces two isomorphic $2$-regular graphs in the final decomposition, and the copy of $X_{2r}$, when it is present, produces three isomorphic $2$-regular graphs in the final decomposition, this construction can produce a wide variety 
of different combinations of $2$-regular graphs in the final decomposition. 

The $2$-regular graphs given by the construction of 
the preceding paragraph will all have the same order, namely $k=2r$, 
but it is also possible to get around this constraint. 
Instead of using a $P_{r+1}$-decomposition of $K_m$ or $K_m-Y_r$, one may use a decomposition of $K_m$ or  $K_m-Y_r$ into paths which are not necessarily all isomorphic. In \cite{Bry} it is shown that the obvious necessary conditions are sufficient for the existence of a decomposition of $K_m$ into paths of any specified lengths. This facilitates the construction of decompositions of $K_n-I$ into many combinations of $2$-regular graphs of many different orders. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection*{Acknowledgements}
%Thanks to Professor Querty for suggesting the proof of
%Lemma~\ref{lem:Technical}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{AdaBryBuc} 
P. Adams, D. Bryant and M. Buchanan, 
A survey on the existence of $G$-designs, 
{\it J. Combin. Des.}, {\bf 16} (2008), 373--410.

\bibitem{AdaBryGav}
P. Adams, D. Bryant and H. Gavlas, 
Decompositions of the complete graph into small 2-regular graphs, 
{\it J. Combin. Math. Combin. Comput.}, 
{\bf 43} (2002), 135--146.

\bibitem{AguElzHakStoYay}
A. Aguado, S. I. El-Zanati, H. Hake, J. Stob and H. Yayla, 
On $\rho$-labeling the union of three cycles, 
{\it Australas. J. Combin.},
{\bf 37} (2007), 155--170.

\bibitem {AlsGav} 
B. Alspach and H. Gavlas, 
Cycle decompositions of $K_n$ and $K_n - I$, 
{\it J. Combin. Theory Ser. B}, 
{\bf 81} (2001), 77--99.

\bibitem{BarKuhLoOst}
B. Barber, D. K\"{u}hn, A. Lo, and D. Osthus, 
Edge-decompositions of graphs with high minimum degree,
{\it Adv. Math.},
{\bf 288} (2016), 337--385. 

\bibitem{BliElz}
A. Blinco and S. I. El-Zanati, 
A note on the cyclic decomposition of complete graphs into bipartite graphs, 
{\it Bull. Inst. Combin. Appl.},
{\bf 40} (2004), 77--82. 

\bibitem{Bry}
D. Bryant, 
Packing paths in complete graphs, 
{\it J. Combin. Theory Ser. B}, 
{\bf 100} (2010), 206--215.

\bibitem{BryDan}
D. Bryant and P. Danziger, 
On bipartite $2$-factorisations of $K_n - I$ and the Oberwolfach problem, 
{\it J. Graph Theory},
{\bf 68} (2011), 22--37.

\bibitem{BryElz} 
D. Bryant and S. El-Zanati, 
Graph decompositions,
in 
{\it The CRC Handbook of Combinatorial Designs, {\rm 2}nd edition} 
(Eds. C. J. Colbourn, J. H. Dinitz), CRC Press, Boca Raton (2007), 477--486.

\bibitem{BryRod}
D. Bryant and C. A. Rodger, 
Cycle Decompositions,
in 
{\it The CRC Handbook of Combinatorial Designs, {\rm 2}nd edition} 
(Eds. C. J. Colbourn, J. H. Dinitz), CRC Press, Boca Raton (2007), 373--382.

\bibitem{BrySch}
D. Bryant and V. Scharaschkin,
Complete solutions to the Oberwolfach problem for an infinite set of orders,
{\it J. Combin. Theory Ser. B},
{\bf 99} (2009), 904--918.

\bibitem{CioCam}
S. M. Cioab\u{a} and P. J. Cameron, 
A graph partition problem, 
{\it Amer. Math. Monthly},
{\bf 122} (2015), 972--982.

\bibitem{ColHorWan1}
C. J. Colbourn, D. Horsley and C.Wang, 
Trails of triples in partial triple systems, 
{\it Des. Codes Cryptogr.},
{\bf 6} (2012), 199--212.

\bibitem{ColHorWan2}
C. J. Colbourn, D. Horsley and C. Wang, 
Colouring Triples in Every Way: A Conjecture,
{\it Quad. Mat.},
{\bf 28} (2012), 257--286.

\bibitem{ColZha}
C. J. Colbourn and S. Zhao,
Maximum Kirkman signal sets for synchronous uni-polar multi-user communication systems,
{\it Des. Codes Cryptogr.},
{\bf 20} (2000), 219--227.

\bibitem{Hag}
R. H\"{a}ggkvist,
A lemma on cycle decompositions,
{\it Ann. Discrete Math.},
{\bf 27} (1985), 227--232.

\bibitem{Par}
C. A. Parker,
Complete bipartite graph path decompositions,
PhD Thesis,
Auburn University,
(1998).

\bibitem{Saj} 
M. \v{S}ajna, 
Cycle decompositions III: complete graphs and fixed length cycles, 
{\it J. Combin. Des.}, 
{\bf 10} (2002), 27--78.

\bibitem{Tar}
M. Tarsi,
Decomposition of a complete multigraph into simple paths: Nonbalanced handcuffed designs,
{\it J. Combin. Theory Ser. A},
{\bf 34} (1983), 60--70.

\bibitem{Tra}
T. Traetta,
A complete solution to the two-table Oberwolfach problems,
{\it J. Combin. Theory Ser. A},
{\bf 120}  (2013), 984--997.

\bibitem{Wil}
R. M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), pp. 647--659. Congressus Numerantium, No. XV, Utilitas Math., Winnipeg,
Man., 1976.



\end{thebibliography}

\end{document}