0
$\begingroup$

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

question

possible solution

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

  • 0
    @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.2012-08-26

1 Answers 1

3

As Rick has noted in a comment, the problem can be solved using the graph's complement. If the complement has more than two connected components, there is no solution. If it has two connected components, find a spanning tree in each. If it has one connected component, find a spanning tree and delete an arbitrary edge in it.