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?


2 Answers 2


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.

  • $\begingroup$ That last statement is wrong, most graphs have odd edge cuts... the incident edges around one odd degree vertex give a very easy example. $\endgroup$ Nov 20, 2013 at 21:34
  • $\begingroup$ But the last statement is correct for even graphs. $\endgroup$ Nov 21, 2013 at 1:40

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.