# finding two trees from a graph

The problem is related to check existence of 2 trees of a graph such that:

1)vertices in 2 trees are disjoint and no vertices are missed

2)Any tree edge cannot be a graph edge of original graph.

I only need to know whether 2 trees can exist or not for now.

Is there any known algorithm for finding such 2 trees?

Any hints/suggestions are welcome

Example:

Graph presented in problem is

possible solution

1,4 and 5 are not on any path in original graph. 2 and 3 are not on any path in original graph.

EDIT:

After reading some graph theory i think above problem essentially translates to concluding whether a graph is bipartite or not. Please correct me ?

Thanks

-
You seem to be using some non-standard terminology here. Certainly vertices $2$ and $3$ are on a path in the original graph -- I suspect that what you mean is that they're not joined by an edge? Also, the trees you show wouldn't usually be called trees of this graph; as far as that phrase is used at all, I would expect it to be used for trees that are subgraphs of the graph. It seems that you're looking for two trees on the vertex set of the graph. – joriki Aug 25 '12 at 18:49
For your (2), do you mean that any tree edge cannot be a graph edge. As joriki noted, your condition is unclear, though your example is consistent with my suggestion. If that's the condition you want, then there's an easy solution, involving a spanning tree (or forest) of the graph's complement. – Rick Decker Aug 25 '12 at 18:59
@joriki i have now corrected as per both your comments – JCH Aug 26 '12 at 6:29
@Rick you are right it is actually tree edge cannot be graph edge. Also i am not interested in tree as first step but just want to know the set of vertices in both sets. – JCH Aug 26 '12 at 6:30