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.