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.
Best Answer
What you need is the following observation/result:
Proposition: A graph is bipartite if and only if the set of vertices/nodes can be partitioned into two subsets in such a way that in a given subset, no two vertices are connected.
Think about it a little while, and it should become clear. But then, you see that a graph without cycles is clearly bipartite. For if you have a tree, choose a root. Then you put this root in one set; you put its neighbours in the second set; you put the neighbours' neighbours in your first set, etc. Since there is no cycle, for any choice of two vertices in a given subset, they won't be adjacent. Now, if you have a forest, partition each tree separately.
This is the way I would prove that a forest is bipartite, but this is only because I am more familiar with the definition involving a partition of the vertex set. On the other hand, for vacuous reasons, a forest is bipartite, exactly because it does not have any odd cycle (since it does not have any cycle). However, sometimes it happens that we are reluctant to believe something is true for vacuous reasons. This is why I wrote the above solution.