Bipartite Graphs Decomposable into Closed Trails

Abstract

Let $G=K_{a,b}$, where $a,b$ are even, or $G=K_{a,a}–M_{2a}$, where $a\ge 1$ is an odd integer and $M_{2a}$ is a perfect matching in $K_{a,a}$. It has been shown ([3,4]) that $G$ is arbitrarily decomposable into closed trails. Billington asked if the graph $K_{r,s}–F$, where $s,r$ are odd and $F$ is a (smallest possible) spanning subgraph of odd degree, is arbitrarily decomposable into closed trails ([2]).

In this article we answer the question in the affirmative.