Is it true that in any (connected) graph $G=(V,E)$, if $T$ is a spanning tree than its complement (edge-wise) may be covered by a union of disjoint cycles?
Here's a non-complete attempt to prove this claim:
- Each edge $e\in E\smallsetminus E(T)$ closes a single cycle if added to $T$
- The number of cycles in $E\smallsetminus E(T)$ of which $e$ is part of is even (I am not sure about that)
- There are no cycles within $T$
- Hence: taking the "sum" modulo 2 of all cycles in the graph (that is, a union with repetitions, discarding all edges which were counted an even number of times) produces a union of cycles which contains all edges of $E\smallsetminus E(T)$.
That's it; the missing part is the second bullet, which I'm not sure that is even true.
For each $e \in E\smallsetminus E(T)$, let $C_e$ be the unique cycle in $T+e$. If you take the "sum" modulo $2$ of all cycle $C_e$ for all $e \in E\smallsetminus E(T)$, you get a subgraph $H$ of $G$ all whose components are Eulerian, hence $H$ is the disjoint union of cycles. Also, $E\smallsetminus E(T) \subset E(H)$ since every $e \in E\smallsetminus E(T)$ is in exactly one cycle $C_e$ therefore it must be in "sum" modulo 2 (i.e $H$)