Yes it does hold. Call two vertices *connected* if there is a finite path between them. The graph consists of one or more connected components. It is enough to prove the result for connected graphs having at least 2 vertices.  So a vertex may have unaccountably many neighbors, however every pair of vertices has a finite shortest path connecting them. 

Assume first that there is a *leaf*,a vertex of degree  one. Label the leaf or leaves with $0$ and every other vertex with the distance to the nearest leaf. So all edges connect vertices who labels differ by $1$ or are equal. Select all edges labelled $2j,2j+1$. If a vertex labelled $2j$ has no neighbors labelled $2j+1,$ then select a single edge on it labelled $2j-1,2j.$ The result is a collection of single edges and stars with an odd label on the center. (We neglected the trivial but important case that there are two vertices.)

If there are no leaves then pick a vertex $u$ , label it with $0$ and temporarily label each other vertex according to distance from $u$. Now delete all but one edge on $u$, keep the labels in the component of $u$ but lower all other labels by $1$, and proceed as above.