On a conjecture of Graham and Häggkvist with the polynomial method

A conjecture of Graham and Häggkvist states that every tree with m edges decomposes every 2m-regular graph and every bipartite m-regular graph. Let T be a tree with a prime number p of edges. We show that if the growth ratio of T at some vertex v₀ satisfies ρ(T,v₀)≥^1/2, where is the golden ratio, then T decomposes K_2p,2p. We also prove that if T has at least p/3 leaves then it decomposes K_2p,2p. This improves previous results by Häggkvist and by Lladó and López. The results follow from an application of Alon’s Combinatorial Nullstellensatz to obtain bigraceful labelings.