We conjecture that, for each tree T there exists a natural number k(T) such that the following holds: If G is a k(T)-edge-connected graph such that \E(T)\ divides \EG)\, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T=K-1,K-3 (the claw), this holds if and only if there exists a (smallest) natural number k(t) such that every k(t)-edge-connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3-flow conjecture says that k(t)=4. We prove the weaker statement that every 4[ log n]-edge-connected graph with n vertices has an edge-decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge-decomposition into claws. (C) 2006 Wiley Periodicals, Inc.