Ear decompositions and spanning trees

Question

I am looking for a reference for the following theorem:

Theorem: Let $G$ be a 2-connected, simple, undirected graph, and let $T$ be a spanning tree. Then $G$ has an ear decomposition in which every ear contains exactly one edge outside $T$.

I am following West's definition of "ear decomposition": an edge decomposition of $G$ into a cycle $C$ and a sequence of paths $P_1,\dots,P_m$, where $P_i$ shares only its endpoints with $C\cup P_1\cup\cdots\cup P_{i-1}$.

I think this is true; the idea is clear but some care is needed with the algorithm. It seems like something that ought to be known, but I have not been able to locate a reference.

Answer 1

This is not a reference, sorry.

The algorithm looks quite straightforward. We require additionally that for the vertex sets $V_0=V(C),V_i=V(C\cup P_1\ldots\cup P_i), i=1,2,\ldots$ the restriction $T(V_i)$ is a tree (well, this is automatically so if each ear contains exactly one edge not from $T$). Start with any edge $e\notin T$ and define $C$ as the unique cycle of $e\cup T$. For the induction step from $V_k$ to $V_{k+1}$, choose any edge $e$ of $T$ which joins some $a\in V_k$ with $b\in V\setminus V_k$. Consider the forest $T\setminus a$. It has several components. Note that $b$ can not be in the same component with some vertex $c\in V_k\setminus a$. Indeed, the only $T$-path from $b$ to $V_k$ is the edge $ba$. Therefore (since the graph $G\setminus a$ is connected) there should be an edge $cd\notin T$ which joins a component containing something from $V_k$ (say, $c$ is in such a component) and a component not containing vertices from $V_k$ (but containing $d$). Add an ear containing $cd$, a $T$-path from $d$ to $a$ and a $T$-path from $c$ to $T(V_k)$.