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
    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.2012-08-25
  • 3
    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.2012-08-25
  • 0
    @joriki i have now corrected as per both your comments2012-08-26
  • 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.