\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amssymb,amsmath,amsthm}
\usepackage{latexsym}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
%\usepackage{epsfig}
%\usepackage{epstopdf}
\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{\proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\ep}{\hfill$\Box$\end{proof}\medskip}

\title{\bf Edge-decomposition of graphs into copies of a tree with four edges}
\author{J\'anos Bar\'at \thanks{Research is supported by OTKA Grants PD~75837 and K~76099, 
Australian Research Council grant DP120100197. and the J\'anos Bolyai Research Scholarship of the
Hungarian Academy of Sciences.}\\[-0.8ex]
\small School of Mathematical Sciences,\\[-0.8ex]
\small Monash University, Victoria 3800 Australia\\
\small and\\
\small MTA-ELTE Geometric and Algebraic Combinatorics Research Group\\[-0.8ex]
\small 1117 Budapest, P\'azm\'any P\'eter s\'et\'any 1/C, Hungary\\
\small \tt{barat@cs.elte.hu}\\
and\\
D\'aniel Gerbner\thanks{Research supported in part by the
Hungarian NSF under contract NK~78439 and PD~109537.}\\
%\and \\
\small Hungarian Academy of Sciences, Alfr\'ed R\'enyi Institute\\[-0.8ex]
\small of Mathematics, P.O.B. 127, Budapest H-1364, Hungary\\
\small \texttt{gerbner@renyi.hu}
}
\date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\
\small Mathematics Subject Classifications: 05C40, 05C51, 05C70}

\begin{document}

\maketitle

\begin{abstract}
We study edge-decompositions of highly connected graphs into copies of a given tree.
In particular we attack the following conjecture by Bar\'at and Thomassen:
for each tree $T$, there exists a natural
number $k_T$ such that if $G$ is a
$k_T$-edge-connected graph, and $|E(T)|$ divides $|E(G)|$,
then $E(G)$ has a decomposition into copies of $T$.
As one of our main results it is sufficient to prove the conjecture for bipartite graphs.
The same result has been independently obtained by Carsten Thomassen JCTB  {\bf 103} (2013), 504--508.

Let $Y$ be the unique tree with degree sequence $(1,1,1,2,3)$.
We prove that if $G$ is a $191$-edge-connected graph of size divisible by $4$, then $G$
has a $Y$-decomposition.
This is the first instance of such a theorem, in which the tree is different from a path or a star.
Recently Carsten Thomassen proved a more general decomposition theorem for bistars, which yields the 
same result with a worse constant. 
\end{abstract}

 \bigskip\noindent \textbf{Keywords:} graph theory, decomposition, tree, edge-connectivity.
\section{Introduction}


Our notations and concepts strictly follow \cite{thomassen2}.
A graph $G$ has an {\it $H$-de\-com\-po\-si\-tion}, if the edges of $G$
can be decomposed into subgraphs isomorphic to $H$.
There is a necessary condition: $|E(H)|$ divides $|E(G)|$.
In what follows, we always assume this hypothesis.
The general problem of $H$-decompositions
was proved to be NP-complete for any $H$ of size greater than 2 by
Dor and Tarsi \cite{dortarsi}.
However Bar\'at and Thomassen \cite{bt} posed the following

\begin{conjecture}\label{conj1}
For each tree $T$, there exists a natural
number $k_T$ such that the following holds: if $G$ is a
$k_T$-edge-connected simple graph such that $|E(T)|$ divides $|E(G)|$,
then $G$ has a $T$-decomposition.
\end{conjecture}

In Section~\ref{enough} we prove that it is sufficient to prove the conjecture for bipartite graphs.
The same result has been independently obtained by Carsten Thomassen \cite{ct4}.

\begin{theorem} \label{paros} Let $T$ be a tree with $t$ edges, where $t>3$. The following two statements are equivalent.\\
(i) There exists a natural number $k_T$ such that for any $k_T$-edge-connected bipartite graph $G$,
 if $t$ divides $|E(G)|$, then $G$ has a $T$-decomposition.\\
(ii) There exists a natural number $k'_T$ such that for any $k'_T$-edge-connected graph $G$,
if $t$ divides $|E(G)|$, then $G$ has a $T$-decomposition.
\end{theorem}

%\medskip

%\noindent {\bf Theorem} \it
%Let $T$ be a tree with $t$ edges, where $t>3$. The following two statements are equivalent.\\
%(i) There exists a natural number $k_T$ such that for any $k_T$-edge-connected bipartite graph $G$,
 %if $t$ divides $|E(G)|$, then $G$ has a $T$-decomposition.\\
%(ii) There exists a natural number $k'_T$ such that for any $k'_T$-edge-connected graph $G$,
%if $t$ divides $|E(G)|$, then $G$ has a $T$-decomposition. \rm

%\medskip

In many cases $k$-edge-connectivity is provided by the existence of $k$ edge-disjoint spanning trees.
Nash-Williams \cite{n-w} and Tutte \cite{tu} independently proved the following converse.

\begin{theorem}\label{nwt}
 If $k$ is a natural number, and $G$ is a $2k$-edge-connected graph,
then $G$ contains $k$ pairwise edge-disjoint spanning trees.
\end{theorem}

At the time of posing there was no tree with at least three edges, for which Conjecture~\ref{conj1} was known to be true.
A nice and thorough introduction to the subject is \cite{thomassen1},
where Thomassen proved that every $207$-edge-connected graph $G$ has a set $E$ of at most $6$
edges such that $G-E$ has a decomposition into paths of length $4$.
Approximately at the same time Thomassen \cite{thomassen2} proved

\begin{theorem}\label{3path} If $G$ is a $171$-edge-connected graph of size divisible
by $3$, then $G$ has a $3$-path-decomposition.
\end{theorem}

Recently Thomassen \cite{ct3} proved the following.

\begin{theorem}
Let $k$ be any natural number. If $G$ is a $(2k^2+k)$-edge-connected graph and $|E(G)|$ is divisible by $k$,
then $G$ has a $K_{1,k}$-decomposi\-tion.
\end{theorem}


It is also mentioned in \cite{ct3} that Conjecture~\ref{conj1} holds for any path with $2^t$ edges.
In view of these results by Thomassen, our Theorem~\ref{fo} is the first confirmation of Conjecture~\ref{conj1}, 
where $T$ is different from a path or a star.
Our result is the following:\\
{\bf Theorem} Let $Y$ denote the tree with degree sequence $(1,1,1,2,3)$. If $G$
is a $191$-edge-connected graph of size divisible by $4$, then $G$
has a $Y$-decomposition.

However, very recently Thomassen proved a more general theorem which gives a decomposition into bistars \cite{ct4}. In his notation our main result is an $S(2,3)$-decomposition. In Thomassen's result the necessary connectivity condition for our case is $784\cdot 2^4=12544$. 

The proof of Theorem~\ref{3path} consists of three main ingredients.
In principle the method could be applied to any tree $T$.
Let $G$ be a graph of sufficiently high edge-connectivity,
and let $T$ be a tree on $k$ edges.
In a nutshell Thomassen set up the following scheme:

\noindent 1. Remove copies of $T$ from $G$ such that a bipartite graph $G[A,B]$ remains with parts $A$ and $B$ that still contains many edge-disjoint spanning trees.\\
2. Remove more copies of $T$ such that each degree in $A$ becomes divisible by $k$,
and the rest still contains some edge-disjoint spanning trees.\\
3. Group the edges from $A$ such that copies of $T$ arise, which altogether decompose
the rest.

It looks natural to use the number of edge-disjoint spanning trees in a condition
instead of edge-connectivity.
We formulate a tempting qualitative conjecture, which is partly inspired by Thomass\'e \cite{stef}.

\begin{conjecture}\label{spt}
Let $T$ be a tree with $t$ edges.
If a graph $G$ contains $t$ edge-disjoint spanning trees and $t$ divides $|E(G)|$,
then $G$ has a $T$-decomposition.
\end{conjecture}

Using a maximum cut idea it is easy to prove the following

\begin{lemma}\label{bipart} If $k$ is a natural number and $G$ is a
$(2k-1)$-edge-connected graph, then $G$ has a partition into $A$ and $B$ such
that $G[A,B]$ is $k$-edge-connected.
\end{lemma}

%The following is a slight improvement of a result from
%\cite{thomassen2} that we make heavy use of.
%The proof is the same as for Proposition 3 in \cite{thomassen2}.
%
%\begin{lem}\label{fontos} Let $p$ be any natural number, and put $m=2^p$. If $G$
%is a graph with a collection of $m$ pairwise edge-disjoint
%spanning  trees, then $G$ has a spanning tree $T$ such that $d_T(v) \le d_G(v)/m+3p/2$ for
%each vertex $v$.
%\end{lem}

We make heavy use of the following result by
Ellingham, Nam and Voss \cite{elli}.

\begin{lemma}\label{env}
If $G$ is an $m$-edge-connected graph, then $G$ has a spanning tree $T$ such that 
$d_T(v) \le \lceil d_G(v)/m\rceil +2$ for each vertex $v$.
\end{lemma}

There is a unique tree with degree sequence $(1,1,1,2,3)$.
For simplicity we call it $Y$.
The vertex of degree 3 in $Y$ is the 3-vertex, and the vertex of degree 2 is the $2$-vertex for any further reference.
In Section~\ref{main} we prove that every $191$-edge-connected graph $G$ has a $Y$-decomposition (Theorem~\ref{fo}).

\begin{figure}[ht]
 \begin{center}
  \includegraphics[scale=0.5]{y_fa.eps}
 \end{center}
  \caption{The unique tree on 5 vertices with a vertex of degree 3}
\label{y_fa}
\end{figure}

These constants in the edge-connectivity are most likely far from optimal.
At the end of the paper we list a few examples indicating some lower bounds.

A path with $k$ edges is a $k$-{\it path} and denoted by $P_{k+1}$.

\section{Making the graph bipartite} \label{enough}

In Thomassen's scheme the first step
is to delete some copies of the tree such that
the remaining graph is a highly edge-connected bipartite graph.
It was mentioned in \cite{thomassen2} that perhaps this method works
for every tree.
In this section we validate this hypothesis.
We need the following result that is practically a consequence of
Lemma~\ref{env}.

\begin{lemma}\label{uj}
For any natural numbers $k,\ell$ and $m$, where $m>3$, if $G$ contains $km^{2\ell}$ edge-disjoint spanning trees, 
then we can choose subgraphs
$M_1\subset M_2\subset \dots \subset M_{\ell}\subset M_{\ell+1}$ such that $M_i$ is the union of $km^{2(i-1)}$ 
edge-disjoint spanning trees and $d_{M_{i}}(v) \le d_{M_{i+1}}(v)/m$
for every vertex $v$ and $1\le i\le \ell$.
\end{lemma}

\begin{proof}
%Let $p$ be an integer such that $2^p\le m^2<2^{p+1}$.
By Lemma~\ref{env} if we are given $m^2$ edge-disjoint spanning trees of $G$, then there exists a spanning tree $T$
such that $d_{T}(v) \le \lceil d_*(v)/m^2\rceil+2$, where $d_*(v)$ is the total degree in that particular 
collection of $m^2$ spanning trees.
Now $\lceil d_*(v)/m^2\rceil+2\le d_*(v)/m$ since $d_*(v)\ge m^2$ and $m>3$.

We prove the Lemma by induction on $\ell$.
We start with the base case $\ell=1$.
If we are given $km^2$ edge-disjoint spanning trees, then we divide them
into $k$ equal sets. Let $S_1,\dots,S_k$ each be the union of the $m^2$ spanning trees in those sets.
By the previous argument there exists a spanning tree $T_i$ in $S_i$
such that $d_{T_i}(v)\le d_{S_i}(v)/m$ for any vertex $v$, where $1\le i\le k$.
Now $M_1:=\cup_{i=1}^kT_i$ and $M_2:=\cup_{i=1}^kS_i$.
Summing all the inequalities yields $d_{M_1}(v)\le d_{M_2}(v)/m$ as required for $\ell=1$.

In the induction step let $\ell>1$.
There are $m^2km^{2(\ell-1)}$ edge-disjoint spanning trees given.
We partition this set of spanning trees into $S_1,\dots,S_{km^{2(\ell-1)}}$ such that each $S_i$ contains $m^2$ spanning trees.
For every $i$ there exists a spanning tree $T_i$ in $S_i$
such that $d_{T_i}(v)\le d_{S_i}(v)/m$, where $1\le i\le km^{2(l-1)}$.
By the induction hypothesis we can find a sequence $M_1\subset M_2\subset \dots \subset M_{\ell}$ in $\cup_{i=1}^{km^{2(\ell-1)}}T_i$ satisfying the conditions of the lemma.
Finally let $M_{\ell+1}=\cup_{i=1}^{km^{2(\ell-1)}}S_i$.
Now $d_{M_{i}}(v) \le d_{M_{i+1}}(v)/m$ is satisfied for every vertex $v$ and $1\le i\le \ell-1$
by the induction hypothesis and for $i=\ell$ by the same summation as in the base case.
\ep

In our paper we only use the disjoint union of spanning trees in $M_i$ to ensure sufficiently large minimum degree.

Now we are ready to prove Theorem \ref{paros}.
%Next we show that it is sufficient to prove Conjecture~\ref{conj1} for bipartite graphs:

%\begin{theorem} \label{paros} Let $T$ be a tree with $t$ edges, where $t>3$. The following two statements are equivalent.\\
%(i) There exists a natural number $k_T$ such that for any $k_T$-edge-connected bipartite graph $G$,
% if $t$ divides $|E(G)|$, then $G$ has a $T$-decomposition.\\
%(ii) There exists a natural number $k'_T$ such that for any $k'_T$-edge-connected graph $G$,
%if $t$ divides $|E(G)|$, then $G$ has a $T$-decomposition.
%\end{theorem}


\begin{proof} We only prove the non-trivial implication.
Let $k'_T=8t^{2t+3}+4k_T-1$.
By Lemma~\ref{bipart} we can find a partition $(A,B)$ of the
vertex set such that the edge-connectivity of $G[A,B]$ is $4t^{2t+3}+2k_T$.
By Theorem~\ref{nwt}
there are at least $2t^{2t+3}+k_T$ pairwise edge-disjoint spanning trees in $G[A,B]$.
In what follows we show how to delete all edges inside $A$ by removing copies of $T$ from $G$ using
at most $t^{2t+3}$ of the spanning trees. We can repeat the same procedure to empty $B$.
After that the remaining $k_T$ spanning trees provide $k_T$-edge-connectivity of the remaining bipartite graph.

First we arbitrarily delete copies of $T$ from $G[A]$ as long as possible.
We partition the remaining edges into subgraphs of $T$ as follows.
In each round we consider subgraphs of $G[A]$ which are isomorphic to subtrees of $T$ and 
choose one with the most number of edges. 
We remove it from the current graph, and start another round on the remaining edges of $G[A]$. 
This way we create a sequence $H_1, \dots, H_r$ of proper subtrees of $T$ such that their union is $G[A]$ and 
their size is monotone decreasing.


Let $H$ be a graph in $\mathcal{H}$. Then there exists a homomorphism $\phi$ from $H$ to $T$.
A vertex $v$ is \emph{unsaturated} in $H$, if the degree of $\phi(v)$ is higher in $T$ than 
the degree of $v$ in $H$. 
Note that since $H$ is isomorphic to a proper subtree of $T$, there is at least one unsaturated 
vertex in $H$. 
However, we claim that for every vertex $v$ in $A$ there are at most $t-1$ trees in $\mathcal{H}$, 
in which $v$ is unsaturated. Indeed,
consider the first occasion that $v$ becomes unsaturated, say in tree $H_i$.
At this point all remaining edges (i.e. edges of $G[A]$ which are not in $H_1, \dots, H_{i-1}$) incident to 
$v$ must be incident only to vertices in $H_i$, otherwise we could add that edge to $H_i$ in order to get a 
larger subtree of $T$.

The size of $H_i$ is at most $t-1$, which shows that after this round, there are at most $t-2$ edges incident to 
$v$, which are in $H_{i+1}, \dots, H_r$. 
This implies that $v$ is in at most $t-2$ trees among those, hence even if it is unsaturated in all of them, 
it is unsaturated at most $t-1$ times.
With a different argument we can prove this to be at most $t/2$, but for simplicity we use $t-1$ in the 
counting below.

\begin{claim}
The set $\mathcal{H}$ can be partitioned into $t^2$ sets
$\mathcal{H}_1, \dots, \mathcal{H}_{t^2}$ such that for each $i$ and each
vertex $v$ in $A$, there is at most one tree in $\mathcal{H}_i$  where
$v$ is unsaturated, $1\le i\le t^2$.
\end{claim}

\begin{proof}
As long as possible we select trees from $\mathcal{H}$ into $\mathcal{H}_1$ without violating the property.
We similarly create $\mathcal{H}_2, \dots ,\mathcal{H}_{t^2}$ in the remainder of $\mathcal{H}$.
If a tree $H$ is not selected into $\mathcal{H}_i$, then one of its vertices violates the property, say $v$.
Necessarily $v$ is unsaturated in a tree that is already put into $\mathcal{H}_i$.
The size of $H$ is at most $t+1$ and $v$ is unsaturated at most $t-1$ times.
Therefore, such a bad event can happen at most $(t+1)(t-1)$ times and the claim holds.
\ep

Back to the proof of Theorem~\ref{paros}:
We save $k_t$ edge-disjoint spanning trees for later, and
partition the remaining available spanning trees into $2t^2$ sets each of which contains $t^{2t+1}$ spanning trees. 
First we complete all trees in $\mathcal{H}_1$ to copies of $T$ using the edges of $t^{2t+1}$ spanning trees only.
We apply Lemma~\ref{uj} with $t=k=\ell=m$ to the graph which is the union of these spanning trees.
(Here $\ell=t-1$ would suffice.)
We get the subgraphs $M_1,\dots, M_{t+1}$ with the properties as in Lemma~\ref{uj}.

We first describe our process for one $H\in \mathcal{H}_1$.
Select all unsaturated vertices of $H$ forming a set $D_0(H)$.
We extend $H$ into a copy of $T$ level by level starting at $D_0(H)$.
In the first step we use the edges from the $t$ edge-disjoint spanning trees that
form $M_1$, to add as many edges between $D_0(H)$ and vertices not in $H$ as needed.
Notice that every vertex in $D_0(H)$ has degree at least $t$ in $M_1$.
Since at most $t$ edges are to be added in total, we can choose to extend the
tree $H$ to $H(1)$ by using edges with pairwise distinct endvertices in $B$.
These new vertices form the set $D_1(H)$ and we produced a larger tree $H(1)$ that is isomorphic to a 
subtree of $T$. Now the only unsaturated vertices of $H(1)$ are these new vertices in $B$.
We next use the edges of $M_2$ to proceed with the completion of $T$.
We know that $d_{M_2}(v)\ge td_{M_1}(v)$.
Therefore, we can choose the edges to complete the next level of $T$ such that
their endvertices (at most $t$) are pairwise disjoint, and
they are distinct from the (at most $t$) vertices in $H(1)$.
Generally in step $(j+1)$ we can use the edges of $M_{j+1}\setminus M_{j}$ to extend
$H(j)$ to $H(j+1)$. Since $d_{M_{j+1}}(v)\ge td_{M_{j}}(v)$, we can avoid creating a cycle
and we can fulfill any demand for an edge.

Instead of a concrete $H$ we do the above process simultaneously for all subtrees in $\mathcal{H}_1$.
Let all unsaturated vertices in $\mathcal{H}_1$ form $D_0(\mathcal{H}_1)$.
We extend each subtree in $\mathcal{H}_1$ to a larger subtree of $T$.
Each vertex of $A$ is unsaturated at most once in $\mathcal{H}_1$ and $d_{M_1}(v)\ge t$ for any vertex $v$.
Therefore, $M_1$ provides a sufficient amount of edges to create a set of subtrees $\mathcal{H}_1(1)$ to complete 
level 1. to add new vertices forming $D_1(\mathcal{H}_1)$.
It might happen that many edges from different vertices of $A$ connect in $M_1$ to a particular vertex $u$ of $B$.
It makes $d_{M_1}(u)$ large, but the growth $d_{M_2}(u)\ge td_{M_1}(u)$ ensures us that we can continue with step 2.

In general in step $j+1$ we extend the trees $H(j)$ to $H(j+1)$.
We form $D_{j+1}(\mathcal{H}_1)$
and create $\mathcal{H}_1(j+1)$ to complete level $(j+1)$.
Consider a vertex $v$, which is on level $j$ in $H(j)$ and possibly in some other trees.
We know that $v$ is on level $j$ in at most $d_{M_j}(v)$ trees.
%We extend the notion of unsaturated vertices: a vertex $v$ of $H(j)\setminus H(j-1)$ is {\it unsaturated}
%if its degree in $H(j)$ (which is exactly 1) is smaller than the degree of the corresponding vertex in $T$.
For each subtree where $v$ is unsaturated we select $(t-1)$ edges of $M_{j+1}\setminus M_j$ incident to $v$.
As $d_{M_{j+1}}(v)\ge td_{M_j}(v)$ we can make the selection such that
every edge is chosen at most once.
We do the same for every vertex in $D_j(\mathcal{H}_1)$.
%the appropriate class $A$ or $B$ depending on the parity of $j$, where the newest unsaturated vertices are.

We use only the selected edges for the extension of the subtrees.
We have to show that any subtree $H(j)$ in $\mathcal{H}_1(j)$ can be extended to $H(j+1)$ using those edges.
Now there might be many unsaturated vertices $v_1, \dots, v_q$ in $H(j)$, but at most $(t-1)$ edges have to be added altogether.
As we selected $t-1$ edges for every $v_i$, we can choose the edges of the next level such that no cycle occurs.
%Indeed, we can add the needed edges greedily, at first those incident to $v_1$, then $v_2$, and so on.
%For every $i\le q$, we cannot use those edges incident to $v_i$ for which the other endpoint is already in the tree,
%but one can easily see that the number of those edges plus the number of edges needed to add is at most $t-1$, hence the other edges are enough.
Two different subtrees $H(j)$ and $H'(j)$ can be extended simultaneously since the selected sets of edges are disjoint.
Therefore, all subtrees of $\mathcal{H}_1(j)$ can be extended to $\mathcal{H}_1(j+1)$ simultaneously.

The proof is completed by repeating the argument for each
$\mathcal{H}_i$ with another sequence $M_1\subset\dots\subset M_{t+1}$ provided by another set
of $t^{2t+1}$ edge-disjoint spanning trees.

We repeat the argument with $B$ and remove all complete copies of $T$.
It yields a bipartite graph that contains the remaining set of $k_t$ edge-disjoint spanning trees, hence it is $k_T$-edge-connected.
\ep

For any fixed tree, the above edge-connectivity condition can be substantially reduced.
For any such improvement, we use the same principal argument, but we can decrease the necessary number of spanning trees,
by using the structure of the fixed tree.
In particular for the graph $Y$ we show the following.

\begin{lemma} \label{jo}
If $G$ is a $(4k+23)$-edge-connected graph, then we can remove some $Y$-copies
such that a bipartite graph with
$k$ edge-disjoint spanning trees remains.
\end{lemma}

\begin{proof}
By Lemma~\ref{bipart} we can find a bipartition $G[A,B]$ of $G$ that is $(2k+12)$-edge-connected.
By Theorem~\ref{nwt} we find $(k+6)$ edge-disjoint spanning trees in $G[A,B]$.
Let $T_1, T_2, T_3$ be three of them.
We remove $Y$-copies from $G[A]$ arbitrarily as long as we can.
What remains in $G[A]$ is a collection of paths, cycles, stars and subgraphs of $K_4$.
We cut each path and each cycle into paths with three edges and a possible shorter path.
We select one of the middle vertices of such a 3-path to be the 3-vertex of a future $Y$-copy.
The idea is to extend these 3-paths into $Y$-copies using $T_1$, and remove them from $G$.
For a 2-path we select one endvertex to be the candidate 3-vertex of $Y$.
For a single edge we select one endvertex to be the candidate 3-vertex of $Y$,
and the other endvertex to be the 2-vertex of $Y$.
We cut the stars into 3-stars and a remaining part, which is a 2-path or a single edge as above.
For a 3-star we select a leaf to be the 2-vertex of $Y$.
Until now any vertex in $A$ is selected at most once.
For any subgraph $H$ of $K_4$ that is different from the previous ones, we do as follows.
We cut $H$ into paths of length at most three such that
after the above selection of 3- and 2-vertices of $Y$, each vertex is used at most once.
This is always possible with one exception, the triangle.

If a vertex of $A$ is selected to be a 3- or 2-vertex of $Y$, then
we extend the subgraph with edges of $T_1$ and $T_2$ to achieve a $Y$-copy
that we remove.
It works fine except for a single edge or a triangle.
In case of a single edge we have to add three additional edges to get a $Y$-copy.
For the vertex selected to be the 3-vertex we use edges from $T_1$ and $T_2$.
Now there exists an edge in $T_1$, $T_2$ or $T_3$ from the other end of the single edge
that avoids creating a cycle, hence it completes to a $Y$-copy that we remove.

In case of a triangle we cut it into a single edge and a 2-path.
We do as above for the single edge, and let $v$ be the vertex selected to be the 2-vertex.
For the 2-path we select $v$ to be the 3-vertex of $Y$.
Since we used one of $T_1-T_3$ for the single edge, there are two edges left
to use.
We create a $Y$-copy and remove it.

We have to execute the same process for $G[B]$, where we use three more spanning trees.
After all a bipartite graph remains that has at least $k$ edge-disjoint spanning trees.
\ep

%\begin{rem}
Even if there are only $(k+5)$ spanning trees in $G[A,B]$, we can delete $Y$-copies using $5$ spanning trees
such that a $k$-edge-connected bipartite graph remains.
It requires a more detailed argument,
and implies an improvement by $4$ in the statement of the Lemma and subsequently in Theorem~\ref{fo}.
%\end{rem}

\section{Proof of the main theorem}\label{main}


We recall an implicit result from \cite{thomassen2}.
The second and third paragraphs on page 291 describe a $P_4$-decomposition of a special
graph. We realised that the vertices of $A$ are used in the decomposition
in a balanced way.

\begin{lemma}\label{vege}
Let $G$ be a $2$-edge-connected bipartite graph with classes $A$ and $B$.
If the degree of each vertex in $A$ is divisible by $3$, then $G$ can be decomposed
into paths with $3$ edges such that each vertex $v$ of $A$ is the
endvertex of $d(v)/3$ paths and middle vertex of $d(v)/3$ paths.
\end{lemma}

We use this lemma in the finishing stage of the next
result that gives a sufficient edge-connectivity condition for $Y$-de\-com\-po\-si\-tions.

\begin{theorem} \label{fo}
Let $Y$ denote the tree with degree sequence $(1,1,1,2,3)$. If $G$
is a $191$-edge-connected graph of size divisible by $4$, then $G$
has a $Y$-decomposition.
\end{theorem}


\begin{proof}
We first apply Lemma~\ref{jo} with $k=42$. As a result we are
given a bipartite graph $G[A,B]$ with 42 edge-disjoint spanning
trees $T_1, \dots, T_{42}$.


In the next step
we delete some copies of $Y$ to make all degrees in $A$ divisible by 4.
In the first phase we achieve that all degrees are even.
Thus, let us call vertices in $A$ of odd degree {\it bad}.
Let $M(1)$ be a subgraph of $G$ that is the union of 7
edge-disjoint spanning trees $T_1, \dots, T_7$. By
Lemma~\ref{env}, $m=7$, $M(1)$ has a spanning tree $T(1)$ such
that for each vertex $v$, $d_{T(1)}(v)\le \lceil d_{M(1)}(v)/7\rceil+2\le
d_{M(1)}(v)/2$, since $d_{M(1)}(v)\ge 7$. Similarly the union
$M(2)$ of 7 spanning trees $T_8, \dots, T_{14}$ contains a
spanning tree $T(2)$ such that
$d_{T(2)}(v)\le d_{M(2)}(v)/2$ for each vertex $v$. The union of $T(1)$ and $T(2)$
contains a spanning Eulerian subgraph $E_1$, i.e. a closed trail which visits every vertex.
For a proof of this, see e.g. \cite{jrp}.

We start a walk on $E_1$ at a bad vertex $u_1$. We construct and delete
$Y$-copies as follows. Let $e_1$ be the edge
adjacent to $u_1$ in $E_1$, and let $e_2, e_3,\dots$ be the edges of $E_1$ in order.
Walking along $e_1$ and $e_2$ we are back in $A$ in a vertex $u_2$.
We continue this way till we arrive to another bad vertex $u_r$.
We selected an edge incident to $u_1$ that we later will remove.
Therefore, when $E_1$ possibly arrives to $u_1$ next time, it is no longer considered a bad vertex.
That is, $u_r\neq u_1$.
For every $i$  with $1\le i \le r-1$ we consider $e_{2i-1}$, $e_{2i}$ and
two edges in $M(1) \cup M(2) \setminus E_1$ that are incident to $u_{i+1}$.
These four edges form a copy of $Y$ that we delete.
In this way we delete an odd number of edges incident to $u_1$ and $u_r$, and an even
number of edges incident to any other vertex in $A$.
Therefore, the number of bad vertices decreases.
A vertex can appear multiple times in the above sequence, but that does not change the
parity of the degree.

Now we continue the walk along $E_1$ and do nothing until we find another pair of bad vertices.
We repeat the above process of removing $Y$-copies between the bad vertices.
Iterating these two steps we finish the Eulerian trail, and all degrees are now even.
There is a small remark that we have to make: there are enough edges in  $M(1) \cup M(2)
\setminus E_1$ to use.
Indeed, whenever the walk arrives to a vertex $v$, it means
there are two incident edges in $E_1$.
Hence we can find two more edges, as the degree of a vertex $v$ in $E_1$ is at most half of the
degree of $v$ in $M(1) \cup M(2)$.

In the second phase all degrees in $A$ are even.
Our goal is to remove some $Y$-copies to make all degrees divisible by 4.
Thus, in this phase we call vertices in $A$ of degree $2\mod 4$ {\it bad}.
As in the first phase we need an Eulerian spanning subgraph for our purposes.
Let $M(3)$ be a subgraph of $G$ that is the union of 9
edge-disjoint spanning trees $T_{15}, \dots, T_{23}$. By
Lemma~\ref{env}, $m=9$, $M(3)$ has a spanning tree $T(3)$ such
that for each vertex $v$, $d_{T(3)}(v)\le \lceil d_{M(3)}(v)/9\rceil+2\le
d_{M(3)}(v)/2-1$, since $d_{M(3)}(v)\ge 9$. Similarly the union
$M(4)$ of the spanning trees $T_{24}, \dots, T_{32}$ contains a
spanning tree $T(4)$ such that for each vertex $v$,
$d_{T(4)}(v)\le d_{M(4)}(v)/2-1$. The union of $T(3)$ and $T(4)$
contains a spanning Eulerian subgraph $E_2$.

On the Eulerian trail we mark the bad vertices.
We start the marking at a bad vertex $b_1$, and mark the bad vertices at the first appearance only.
We get a list $b_1,\dots ,b_r$ of bad vertices, and this list
reflects their order of first appearance on $E_2$.
This direction on $E_2$ is fixed from now on.

In what follows we remove $Y$-copies to achieve that all degrees in $A$ are divisible by $4$.
If $v$ is a bad vertex, then we remove 2 or 6 edges incident to $v$ during the process,
when we arrive to the marked copy of $v$.
If $x$ is an unmarked vertex, then we remove precisely 4 edges.
If $x$ is a vertex on $E_2$, then let $x^+$ be the next vertex of $A$ on $E_2$.
There are two building blocks:\\
1. \it the removal of a $Y$-copy at $x$ \rm is a step, when two consecutive edges of $E_2$ starting at $x$,
and two edges of $M(3) \cup M(4) \setminus E_2$ at $x^+$ are removed.\\
2. \it the removal of a reversed $Y$-copy at $x$ \rm is a step, when two consecutive edges of $E_2$ starting at $x$,
and two edges of $M(3) \cup M(4) \setminus E_2$ at $x$ are removed.

We start at $b_1$ and remove a $Y$-copy.
We continue along $E_2$ and remove all edges of $E_2$ two by two.
Every such pair of edges corresponds to a $2$-path in a $Y$-copy, where one end is the $3$-vertex.
The only decision to make is the placement of the other two edges from $M(3) \cup M(4) \setminus E_2$, either at the current vertex $x$ or at the subsequent vertex $x^+$.
This is actually automatic, according to the degree condition:
we either deleted 1 or 3 edges at $x$ due to the previous $Y$-copy,
and our goal might be to remove 2, 4 or 6 edges in total (as our goal is to remove either 0 or 2 edges modulo 4).
If we need to remove one more edge at $x$, then we remove a $Y$-copy.
If we need to remove three more edges at $x$, then we remove a reversed $Y$-copy.
Notice here that finishing the Eulerian trail we get back to $b_1$.
The last condition automatically removes one more edge at $b_1$, since
the remaining number of edges has to be divisible by 4.

After this process bad vertices become good, and the degrees
of good vertices are still divisible by $4$.
Here we also remark that there are enough edges in $M(3) \cup M(4)
\setminus E_2$ to use every time the walk arrives to a vertex $v$.
This again follows from the upper bound on $d_{T(3)}$ and $d_{T(4)}$.
Whenever we arrive to $v$, it means there are two edges incident to $v$ in $E_2$, and we usually
need two edges in $M(3) \cup M(4)
\setminus E_2$. If that vertex is bad, we might need four edges in $M(3) \cup M(4)
\setminus E_2$, but only once (and then it becomes good).
Therefore, we need the degree of $v$ in $M(3)
\cup M(4) \setminus E_2$ to be at least $d_{E_2}(v)+2$, which is satisfied.

We are left with a bipartite graph which we denote by $M[A,B]$. Here all degrees in
$A$ are divisible by 4. Let $M(5)$ be the union of 5 spanning
trees $T_{33}, \dots, T_{37}$. By Lemma~\ref{env}, $m=5$,
$M(5)$ contains a spanning tree $T(5)$ such that for each vertex
$v$, $d_{T(5)}(v)\le \lceil d_{M(5)}(v)/5\rceil+2\le
3d_{M(5)}(v)/4$, since $d_{M(5)}(v)\ge 5$.
We similarly define $M(6)$ and find $T(6)$.
Now for every vertex $v$ in $A$, the following holds:
$d_{T(5)}(v)+d_{T(6)}(v) \le 3d_M(v)/4$. For every vertex $v$ in
$A$ we put aside $1/4$ of the edges such that $T(5)$ and
$T(6)$ remains in the graph. Note that there is no rounding here, hence the remaining graph $M'$ satisfies
the conditions of Lemma~\ref{vege}.

Therefore, we can decompose $M'$ into paths of length 3 such that
for a vertex $v$ with degree $4d$ in $M$ (hence degree $3d$ in the
smaller graph $M'$), there are $d$ paths starting from $v$, and $d$
paths, where $v$ is a middle vertex.
For every vertex $v$ we glue
the $d$ edges, which we put aside in the beginning of the third
phase, one by one to the $d$ paths, where $v$ is a middle vertex.
This gives us a $Y$-decomposition.
\ep


\section*{Discussion}

The edge-connectivity constants in the solved cases of Conjecture~\ref{conj1}
are apparently far from best possible.
There is very little known about lower bounds.
For trees with three edges:
if $T$ is the $3$-path, then there is a $2$-edge-connected graph without a $3$-path-decomposition \cite{jrp}.
In \cite{bt}, there is a $4$-edge-connected graph without a $3$-star-decomposition.
Figure~\ref{letra} shows a $3$-edge-connected bipartite graph with 27 edges and
without a $3$-star-decomposition.

\begin{figure}[ht]
 \begin{center}
  \includegraphics[scale=0.5]{letra.eps}
 \end{center}
  \caption{A bipartite graph without $3$-star-decomposition}
\label{letra}
\end{figure}

There are three different trees with four edges: the $4$-star, the $4$-path and $Y$. We present lower bounds for these trees.
Consider a $C_4$ and replace every vertex by a $K_6$ and every edge by three edges such a way that we get a 6-regular graph.
This is a $6$-edge-connected graph without a $4$-star-decomposition.

Figure~\ref{no_p5} shows a $3$-edge-connected graph
without $P_5$-decomposition.

\begin{figure}[ht]
 \begin{center}
  \includegraphics[scale=0.5]{no_p5.eps}
 \end{center}
  \caption{A graph without $4$-path-decomposition}
\label{no_p5}
\end{figure}

The $4$-wheel is a $3$-edge-connected graph without a $Y$-decomposition.

One might feel that using the edge-connectivity instead of the number of spanning trees and applying
Theorem~\ref{nwt} and Lemma~\ref{bipart} is too generous.
About the sharpness of Theorem~\ref{nwt}, see \cite{cat}.

\section*{Acknowledgements}

We are greatly indebted to the organisers (Bal\'azs Patk\'os and D\"om\"ot\"or P\'alv\"olgyi) of  the  $2^{nd}$ Eml\'ekt\'abla Workshop January 24-27. 2011,
 Gy\"on\-gy\"os\-tarj\'an, Hungary, where the presented research  initiated.
We would like to thank the anonymous referees who pointed out some possible improvements.
% of an earlier version of Lemma~\ref{uj}
%and Theorem~\ref{paros}.




\begin{thebibliography}{99}

\bibitem{bt}
%\textsc{
J.~Bar\'at, C.~Thomassen,
Claw-decompositions and Tutte-orienta\-tions,
%{\em
J Graph Theory 52 (2006), 135--146.

\bibitem{cat}
P. A. Catlin,
Edge-connectivity and edge-disjoint spanning trees, preprint (2005), 4 pages.
See: \url {http://math.wvu.edu/~hjlai/Pdf/Catlin_Pdf/Catlin49a.pdf}

\bibitem{dortarsi}
%\textsc{
D. Dor, M. Tarsi,
Graph-decomposition is NP-complete: a
complete proof of Holyer's conjecture,
SIAM J Comput 26
(1997), 1166--1187.

\bibitem{elli}
M. N. Ellingham, Y. Nam, H-J. Voss,
Connected $(g,f)$-factors.
J Graph Theory 39 (2002), no. 1, 62--75.

\bibitem{jrp}
M. J\"unger, G. Reinelt and W. R. Pulleyblank,
On partitioning the edges of graphs into connected subgraphs,
J. Graph Theory 9 (1985), 539--549.

\bibitem{n-w}C. St. J. A. Nash-Williams,
Edge-disjoint spanning trees of finite graphs,
J London Math Soc 36 (1961), 445--450.

\bibitem{stef}
S. Thomass\'e, private communication.

\bibitem{thomassen1}
%\textsc{
C. Thomassen,
Edge-decompositions of highly connected graphs,
Abh Math Semin Univ Hamburg 18 (2008), 17--26.

\bibitem{thomassen2}
C. Thomassen,
Decompositions of highly connected graphs into paths of length $3$,
J Graph Theory 58 (2008), 286--292.


\bibitem{ct3}
C. Thomassen,
The weak $3$-flow conjecture and the weak circular flow conjecture,
J Combin Theory Ser. B  102 (2012), 521--529.

\bibitem{ct4}
C. Thomassen,
Decomposing a graph into bistars.
J Combin Theory Ser. B  103 (2013), 504--508.

\bibitem{tu} W. T. Tutte,
On the problem of decomposing a graph into $n$ connected factors,
J London Math Soc 36 (1961), 221--230.



\end{thebibliography}


\end{document}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{example}[theorem]{Example}
\newtheorem{conclusion}[theorem]{Conclusion}
