Correspondence between spanning Trees and Even Subgraphs in a Graph

Question

Let $G$ be a connected graph and $T$ a spanning tree of $G$. For $e \in E(G) - E(T)$, Let $C_{e}$ denote the unique cycle in $T + e$.

Let $H(T)$ be the the subgraph of $G$ induced by symmetric difference of of all the $C_{e}$ where $e \in E(G) - E(T)$. One could see that $E(G) - E(T) \subset E(H(T))$ and that $H(T)$ is an even subgraph.

My questions are:

1)Characterize the even subgraphs $K$ of $G$ such that there is a tree $T$ of $G$ and $H(T) = K$.

2) For which tree $T$ and $T'$ we have $H(T) = H(T')$?

3) If $G$ is even connected graph, is $G = H(T)$ for some tree $T$ of $G$? If not what other conditions needed for that to be true?

Answer 1

Well, I might be totally off again, but I think that for every spanning tree $T$ we get $H(T)=G$. As you have already written, obviously $E(G)-E(T)\subset E(H(T))$. For a tree edge, $e\in E(T)$, denote the vertices of the two components of $T\setminus \{e\}$ by $A$ and $B$. Now we have $e\in E(H(T))$ if and only if the number of edges between $A$ and $B$ is odd in $G$ (not counting $e$). But the number of edges between $X$ and $V\setminus X$ is always even in an even graph, so we are done.

Answer 2

Look at the graph with edge set $E'(T)=E(G)-E(H(T))$. It is a forest (since $E'(T)\subseteq E(T)$), and the set of its odd vertices coincides with the set $V_1$ of odd vertices of $G$. In particular, if $G$ is even then this forest should contain no edges (as domotorp has already showed).

Next, I claim that each tree $T$ contains a unique subset $F(T)\subseteq E(T)$ such that $E(G)-F(T)$ is even. Indeed, one such set is $E'(T)$. On the other hand, the existence of the edge $uv$ in $F(T)$ is determined by the parity of the number of vertices from $V_1$ in (any) component of $T-\{uv\}$.

This yields that $H(T)=H(T')$ if and only if $F(T)=F(T')$. This provides a fast algorithm of checking this property: $F(T)$ can be found pretty fast, and then one just needs to check whether $F(T)\subseteq E(T')$ (then necessarily $F(T')=F(T)$).

Finally, take any forest $F$ such that $G-F$ is even. Then $F$ lies in some tree $T$, and $F(T)=E(F)$. Therefore, each even subgraph $K$ such that $E(G)-E(K)$ is a forest is realizable as $H(T)$.