Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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


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.


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


share|improve this question
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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