# Is every forest with more than one node a bipartite graph?

This is a question from my exam today:

The definition of a bipartite graph is: "A graph with at least two nodes is bipartite if and only if there is no odd-length cycle in the graph."

We'll remember that in a forest, and a tree in particular, there are no cycles at all.

Which of the following is true?

1) Every forest with more than one node is a bipartite graph.

2) The previous statement is false, but every tree with more than one node is a bipartite graph.

3) A tree with an odd number of nodes is never a bipartite graph.

4) None of the previous statements are true.

I chose 1, more for logic-based reasons than graph theory-based reasons.. A bipartite graph was defined as a graph with no odd-length cycle in the graph; a forest was defined as a graph with no cycles - ergo a forest is a bipartite graph. (All this is under the assumption that the forest has two or more nodes)

There is currently an argument as to whether the answer is 1 or 4 - the argument behind 4 being that a forest can have unconnected nodes; I don't see this as as a contradiction to the possibility that the forest is a bipartite graph, but other people do.

I'd appreciate some clarification here :). Thanks in advance.

-
It seems to me that 1) is correct for exactly the reasons you say. (I also agree that the question as stated is testing almost no graph theoretic knowledge, but only basic logic.) – Pete L. Clark Jul 16 '12 at 19:55