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